Submission #1029946

#TimeUsernameProblemLanguageResultExecution timeMemory
1029946andrewpBootfall (IZhO17_bootfall)C++14
100 / 100
772 ms8056 KiB
//Dedicated to my love, ivaziva #include <bits/stdc++.h> using namespace std; #define ll int64_t #define ar array #define dbg(x) cerr << #x << ": " << x << "\n"; const ll mxN=503; const ll MOD=3657500101; ll n, a[mxN], dp[mxN*mxN][2], brM[mxN*mxN]; void add(ll& a, ll b) { a+=b; if(a>MOD) a-=MOD; } void sub(ll& a, ll b) { a-=b; if(a<0) a+=MOD; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; ll sum=0; for(ll i=1; i<=n; ++i) { cin >> a[i]; sum+=a[i]; } // n=500; // for(ll i=1; i<=n; ++i) { // a[i]=500; // sum+=a[i]; OVERFLOW!!!! // } for(int i=0; i<mxN*mxN; ++i) { for(int j=0; j<2; ++j) { dp[i][j]=0; } brM[i]=0; } dp[0][0]=1; for(ll i=1; i<=n; ++i) { for(ll s=mxN*mxN-1; s>=a[i]; --s) { add(dp[s][0], dp[s-a[i]][0]); } } if(sum%2==1) { cout << 0 << "\n"; return 0; } if(dp[sum/2][0]==0) { cout << 0 << "\n"; return 0; } vector<ll> ans; for(ll i=1; i<=n; ++i) { for(ll s=0; s<mxN*mxN; ++s) { dp[s][1]=dp[s][0]; } for(ll s=0; s<mxN*mxN-a[i]; ++s) { sub(dp[s+a[i]][1], dp[s][1]); } for(ll s=0; s<mxN*mxN; ++s) { ll get=s+sum-a[i]; if((get%2==0)&&(get/2>=s)&&(dp[get/2-s][1]>0)) { ++brM[s]; if(brM[s]==n) ans.push_back(s); } } } cout << ans.size() << "\n"; for(ll x:ans) cout << x << " "; cout << "\n"; return 0; }
#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...