QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212234#5475. Make a LoopNATURAL6WA 1ms4072kbC++14898b2023-10-13 12:39:222023-10-13 12:39:23

Judging History

你现在查看的是最新测评结果

  • [2023-10-13 12:39:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4072kb
  • [2023-10-13 12:39:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int qread()
{
	int a=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){(a*=10)+=(ch^48);ch=getchar();}
	return a*f;
}
int T,n,r[110],sum,op,vis[110];
bitset<500001>pre[110],s,suf;
int main()
{
	T=1;
	while(T--)
	{
		n=qread();op=sum=0;
		for(int i=1;i<=n;++i)r[i]=qread(),sum+=r[i],vis[i]=0;
		if(sum%2||n%2)
		{
			puts("No");
			continue; 
		}
		sum>>=1;pre[0].reset();pre[0].set(0);s.reset();s.set(0);
		for(int i=1,p;i<=n;++i)
		{
			pre[i]=pre[i-1]|(pre[i-1]<<r[i]);
			if(pre[i][sum])
			{
				p=sum;
				for(int j=i;j;--j)if(pre[j][p]&&p)s|=(s<<r[j]),p-=r[j],vis[j]=1;
				break;
			}
		}
		suf.reset();suf.set(0);
		for(int i=1;i<=n;++i)if(!vis[i])suf|=(suf<<r[i]);
		if((s&suf).count()>1)op=1;
		if(op)puts("Yes");
		else puts("No");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3916kb

input:

4
1 1 1 1

output:

Yes

result:

ok single line: 'Yes'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4072kb

input:

6
1 3 1 3 1 3

output:

Yes

result:

ok single line: 'Yes'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3980kb

input:

6
2 2 1 1 1 1

output:

Yes

result:

wrong answer 1st lines differ - expected: 'No', found: 'Yes'