Submission #969884

#TimeUsernameProblemLanguageResultExecution timeMemory
969884starchanBootfall (IZhO17_bootfall)C++17
65 / 100
1056 ms13580 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define in array<int, 2> #define pb push_back #define pob pop_back #define INF (int)1e17 #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) const int mod = 1e9+33; const int SMX = 2e5+5e4+10; const int MX = 5e5+10; int dp[MX]; void add(int x) { for(int i = MX-1; i >= x; i--) { dp[i]+=dp[i-x]; dp[i]%=mod; } return; } void rem(int x) { for(int i = x; i < MX; i++) { dp[i]-=dp[i-x]; dp[i]+=mod; dp[i]%=mod; } return; } int l[MX]; int r[MX]; int st; void kill(int x) { if(x == st) st = r[st]; else { r[l[x]] = r[x]; l[r[x]] = l[x]; } } signed main() { fast(); for(int i = 1; i < MX; i++) { l[i] = i-1; r[i] = i+1; } r[0] = 1; dp[0] = 1; int n; cin >> n; int S = 0; vector<int> a(n+1); for(int i = 1; i <= n; i++) { cin >> a[i]; S+=a[i]; add(a[i]); } if(S%2 || (dp[S/2] == 0)) { cout << "0\n"; return 0; } for(int i = 1; i <= n; i++) { rem(a[i]); for(int V = st; V < SMX; V = r[V]) { int D = S+V-a[i]; if(D%2) kill(V); if(dp[(D/2)] || ((D >= 2*V) && ((dp[(D/2)-V])))) continue; kill(V); } add(a[i]); } vector<int> v; for(int V = st; V < SMX; V = r[V]) v.pb(V); cout << v.size() << "\n"; for(int x: v) 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...