QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301637 | #5475. Make a Loop | DAleksa | WA | 5ms | 5396kb | C++14 | 945b | 2024-01-10 03:56:21 | 2024-01-10 03:56:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int S=5e5+1;
const int N=100,MX=63;
int n;
int a[N];
int sum;
short int dp[2][S];
bool mark[2][S];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
sum+=a[i];
}
sort(a,a+n);
reverse(a,a+n);
if(n&1){
cout<<"No";
return 0;
}
if(sum&1){
cout<<"No";
return 0;
}
dp[0][0] = 1;
for(int i=0;i<n;++i){
if(mark[0][sum/2]>=4){
cout<<"Yes";
return 0;
}
for(int s=S;s>=a[i];--s){
if(!mark[0][s])dp[0][s]+=dp[1][s-a[i]];
if(dp[0][s]>MX)mark[0][s]=true;
if(!mark[1][s])dp[1][s]+=dp[0][s-a[i]];
if(dp[1][s]>MX)mark[1][s]=true;
}
}
if(mark[0][sum/2]>=4)cout<<"Yes";
else cout<<"No";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 5396kb
input:
4 1 1 1 1
output:
No
result:
wrong answer 1st lines differ - expected: 'Yes', found: 'No'