Submission #406041

#TimeUsernameProblemLanguageResultExecution timeMemory
406041codebuster_10Bootfall (IZhO17_bootfall)C++17
65 / 100
1095 ms31108 KiB
#include <bits/stdc++.h> using namespace std ; #define int int64_t //be careful about this #define endl "\n" #define f(i,a,b) for(int i=int(a);i<int(b);++i) #define pr pair #define ar array #define fr first #define sc second #define vt vector #define pb push_back #define eb emplace_back #define LB lower_bound #define UB upper_bound #define PQ priority_queue #define sz(x) ((int)(x).size()) #define all(a) (a).begin(),(a).end() #define allr(a) (a).rbegin(),(a).rend() #define mem0(a) memset(a, 0, sizeof(a)) #define mem1(a) memset(a, -1, sizeof(a)) template<class A> void rd(vt<A>& v); template<class T> void rd(T& x){ cin >> x; } template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;} template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;} template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template<typename T> void __p(T a) { cout<<a; } template<typename T, typename F> void __p(pair<T, F> a) { cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; } template<typename T> void __p(std::vector<T> a) { cout<<"{"; for(auto it=a.begin(); it<a.end(); it++) __p(*it),cout<<",}\n"[it+1==a.end()]; } template<typename T, typename ...Arg> void __p(T a1, Arg ...a) { __p(a1); __p(a...); } template<typename Arg1> void __f(const char *name, Arg1 &&arg1) { cout<<name<<" : "; __p(arg1); cout<<endl; } template<typename Arg1, typename ... Args> void __f(const char *names, Arg1 &&arg1, Args &&... args) { int bracket=0,i=0; for(;; i++) if(names[i]==','&&bracket==0) break; else if(names[i]=='(') bracket++; else if(names[i]==')') bracket--; const char *comma=names+i; cout.write(names,comma-names)<<" : "; __p(arg1); cout<<" | "; __f(comma+1,args...); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(cin.failbit); cout.precision(15); cout << fixed; #ifdef ONLINE_JUDGE if(sz(s)){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } #define __f(...) 0 #endif } const int N = 500 + 1; bitset<N*N> ans, EMPTY, now, can, check, L[N], R[N];; signed main(){ setIO() ; int n; rd(n); vt<int> a(n); for(auto& i : a) cin >> i; int total = accumulate(all(a),0); { check[0] = true; for(auto i : a){ check |= check << i; } if(total%2 == 1 || !check[total/2]){ cout << 0; exit(0); } } for(int i = 0; i < N*N; ++i){ ans[i] = true; } L[0][0] = 1; for(int i = 1; i < n; ++i){ L[i] = L[i-1] | (L[i-1] << a[i-1]); } R[n-1][0] = 1; for(int i = n-2; i >= 0; --i){ R[i] = R[i+1] | (R[i+1] << a[i+1]); } // optimization for to get runtime/2 for(int i = 0; i < n; ++i){ if(i < n/2){ now = R[i]; for(int j = 0; j < i; ++j){ now |= now << a[j]; } }else{ now = L[i]; for(int j = i+1; j < n; ++j){ now |= now << a[j]; } } int sum = total - a[i]; can = EMPTY; for(int i = now._Find_first(); i < int(now.size()); i = now._Find_next(i)){ int j = abs(2*i - sum); can[j] = true; } ans &= can; } cout << int(ans.count()) << endl; for(int i = ans._Find_first(); i < int(ans.size()); i = ans._Find_next(i)){ 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...