Submission #665572

#TimeUsernameProblemLanguageResultExecution timeMemory
665572AstraytBootfall (IZhO17_bootfall)C++17
100 / 100
401 ms7280 KiB
//君の手を握ってしまったら //孤独を知らないこの街には //もう二度と帰ってくることはできないのでしょう //君が手を差し伸べた 光で影が生まれる //歌って聞かせて この話の続き //連れて行って見たことない星まで //さユリ - 花の塔 #include <bits/stdc++.h> using namespace std; typedef long long ll; //#define int ll #define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define pii pair<int,int> #define pb push_back #define ff first #define ss second #define mp make_pair #define maxn 200005 #define mod 1000000007 void solve(){ int n, sum = 0; cin >> n; vector<int> v(n); for(auto &x:v) cin >> x, sum += x; sort(v.begin(), v.end()); bitset<250005> dp; dp[0] = 1; for(int i = 0; i < n; ++i) dp |= (dp << v[i]); if(sum % 2 == 1 || dp[sum / 2] == 0){ cout << "0\n"; return; } vector<int> cnt(sum + 1, 0); for(int k = 0; k < n; k += 25){ int nxt = min(k + 25, n); bitset<250005> cur; cur[0] = 1; for(int i = 0; i < k; ++i){ cur |= (cur << v[i]); } for(int i = nxt; i < n; ++i){ cur |= (cur << v[i]); } for(int j = k; j < nxt; ++j){ bitset<250005> b = cur; for(int i = k; i < nxt; ++i){ if(j == i) continue; b |= (b << v[i]); } for(int val = sum - v[j]; val >= 0; --val){ if(b[val]) { int t = val - (sum - val - v[j]); if(t <= 0) break; cnt[t]++; } } } } set<int> st; for(int i = 0; i <= sum; ++i){ if(cnt[i] == n) st.insert(i); } cout << st.size() << '\n'; for(auto x:st) cout << x << ' '; } signed main(){ starburst int t = 1; //cin >> t; while(t--) solve(); }
#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...