QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#301638 | #5475. Make a Loop | DAleksa | WA | 3ms | 5780kb | C++14 | 944b | 2024-01-10 03:56:44 | 2024-01-10 03:56:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int S=5e5+1;
const int N=100,MX=3;
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;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 5780kb
input:
4 1 1 1 1
output:
No
result:
wrong answer 1st lines differ - expected: 'Yes', found: 'No'