求助昨晚CF div.2 C
  • 板块学术版
  • 楼主x1489631649
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/8/29 08:27
  • 上次更新2025/8/29 15:15:03
查看原帖
求助昨晚CF div.2 C
780505
x1489631649楼主2025/8/29 08:27

感觉是正解但是找不到错误样例

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200005],f[200005],num[200005],st[200005],nxt[200005],flag[200005];
signed main()
{
	int t;
	scanf("%lld",&t);
	f[0]=0;
	while(t--)
	{
		memset(num,0,sizeof(num));
		memset(flag,0,sizeof(flag));
		int n,x;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=n;i>=1;i--)
		{
			nxt[i]=flag[a[i]];
			flag[a[i]]=i;
		}
		for(int i=1;i<=n;i++)
		{
			x=a[i];
			f[i]=f[i-1];
			if(num[x]==0)
				st[x]=i;
			num[x]++;
			if(num[x]==x)
			{
				if(f[st[x]-1]+x>f[i])
				{
					f[i]=f[st[x]-1]+x;
					num[x]=0;
					st[x]=0;
				}
				else {
					num[x]--;
					st[x]=nxt[st[x]];
				}
			}
		}
		int maxx=-1e9;
		for(int i=1;i<=n;i++)
			maxx=max(maxx,f[i]);
		printf("%lld\n",maxx);
	}
}
/*
1
6
3 2 3 3 2 2
*/
2025/8/29 08:27
加载中...