# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
501221 | luka1234 | Bootfall (IZhO17_bootfall) | C++14 | 616 ms | 4444 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int dp[250001];
int d[250001];
int six[250001];
int main(){
int n;
cin>>n;
int a[n+1];
int sum=0;
for(int k=1;k<=n;k++){
cin>>a[k];
sum+=a[k];
}
if(sum%2==1){
cout<<0;
return 0;
}
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=250000;j>=0;j--){
if(j>=a[i])
dp[j]+=dp[j-a[i]];
}
}
if(dp[sum/2]==0){
cout<<0;
return 0;
}
vector<int> ans;
for(int i=1;i<=n;i++){
for(int j=0;j<a[i];j++)
d[j]=dp[j];
for(int j=a[i];j<=250000;j++){
d[j]=dp[j]-d[j-a[i]];
}
for(int j=1;j<=250000;j++){
if(d[j]==0)
continue;
int x=2*j+a[i]-sum;
if(x>0){
six[x]++;
if(six[x]==n)
ans.push_back(x);
}
}
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<"\n";
for(int k=0;k<ans.size();k++)
cout<<ans[k]<<' ';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |