Submission #1183298

#TimeUsernameProblemLanguageResultExecution timeMemory
1183298AlgorithmWarriorBootfall (IZhO17_bootfall)C++20
65 / 100
1094 ms5228 KiB
#include <bits/stdc++.h> using namespace std; int const MOD=1000000007; int const ORIG=251005; int const MAX=505; int nou[2*ORIG]; int vechi[2*ORIG]; int n; int v[MAX]; vector<int>ans; bool sol[ORIG]; void add_knapsack(int nr){ int i; for(i=0;i<2*ORIG;++i) vechi[i]=nou[i]; for(i=nr;i<2*ORIG-nr;++i) nou[i]=(vechi[i-nr]+vechi[i+nr])%MOD; } void delete_knapsack(int nr){ int i; for(i=0;i<2*ORIG;++i) vechi[i]=nou[i]; for(i=2*nr;i<2*ORIG;++i) nou[i]=(vechi[i-nr]-nou[i-2*nr]+MOD)%MOD; } void read(){ cin>>n; int i; for(i=1;i<=n;++i) cin>>v[i]; } void init(){ nou[ORIG]=1; int i; for(i=1;i<=n;++i) add_knapsack(v[i]); } void solve(){ if(!nou[ORIG]) return; int i,j; for(i=0;i<ORIG;++i) sol[i]=1; for(i=1;i<=n;++i){ delete_knapsack(v[i]); for(j=0;j<ORIG;++j) sol[j]&=(nou[ORIG-j] || nou[ORIG+j]); add_knapsack(v[i]); } for(i=0;i<ORIG;++i) if(sol[i]) ans.push_back(i); } void write(){ cout<<ans.size()<<'\n'; for(auto val : ans) cout<<val<<' '; } int main() { read(); init(); solve(); write(); 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...