| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1352156 | Newtonabc | Bootfall (IZhO17_bootfall) | C++20 | 718 ms | 15996 KiB |
#include<bits/stdc++.h>
using namespace std;
const int N=125010;
bitset<N> dp[510],sf[510];
int a[600];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
int sum=0;
dp[0][0]=1;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]|(dp[i-1]<<a[i]);
}
if(sum%2==1 || dp[n][sum/2]==0){
cout<<0;
return 0;
}
for(int i=1;i<=n;i++){
vector<int> v;
for(int j=1;j<=n;j++) if(j!=i) v.push_back(a[j]);
dp[0]=0;
dp[0][0]=1;
for(int j=1;j<n;j++){
dp[j]=dp[j-1]|(dp[j-1]<<v[j-1]);
}
sf[i]=dp[n-1];
}
vector<int> ans;
for(int i=1;i<=sum;i++){
bool ok=1;
int ts=sum+i;
for(int j=1;j<=n;j++){
int tar=ts-a[j];
if(tar%2==1 || sf[j][tar/2]==0){
ok=false;
break;
}
}
if(ok) ans.push_back(i);
}
cout<<ans.size() <<"\n";
for(int i=0;i<ans.size();i++) cout<<ans[i] <<" \n"[i==(int)ans.size()-1];
}| # | 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... | ||||
