QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#212234 | #5475. Make a Loop | NATURAL6 | WA | 1ms | 4072kb | C++14 | 898b | 2023-10-13 12:39:22 | 2023-10-13 12:39:23 |
Judging History
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'