Submission #169701

#TimeUsernameProblemLanguageResultExecution timeMemory
169701DovranBootfall (IZhO17_bootfall)C++11
13 / 100
3 ms380 KiB
#include <bits/stdc++.h> #define N 100009 #define pii pair <int, int> #define ff first #define ss second #define pb push_back #define ll long long using namespace std; int n, m, v[N], sum, vis[N], ism; int an[N]; vector<int>ans; int main(){ cin >> n; for(int i=1; i<=n; i++) cin>>v[i], sum+=v[i]; vis[0] = 1; for(int i = 1; i <= n;i++) for(int j = sum; j >= 0; j--) vis[j+v[i]] += vis[j]; if(sum%2==1 or vis[sum/2]==0) return cout<<0, 0; for(int i = 1; i <= n; i++){ for(int j = v[i]; j <= sum;j++) vis[j] -= vis[j - v[i]]; for(int j = 1; j < sum; j++){ if(an[j]<i-1) continue; ism = sum - v[i] + j; if(ism % 2 == 0 and ism / 2 - j >= 0 and vis[ism / 2 - j]>0 and vis[ism / 2]>0) an[j]++; // cout<<v[i]<<' '<<j<<' '<<an[j]<<' '<<ism<<endl; } for(int j = sum; j >= v[i]; j--) vis[j] += vis[j - v[i]]; } for(int i = 1; i <= sum; i++) if(an[i] == n) ans.pb(i); cout<< ans.size() <<'\n'; for(auto i : ans) cout<< i <<' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...