제출 #767191

#제출 시각아이디문제언어결과실행 시간메모리
767191TrunktyBootfall (IZhO17_bootfall)C++14
0 / 100
6 ms4180 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll int n,tot; int arr[505],dp[250005],curr[250005]; bitset<250005> bs[505]; signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i=1;i<=n;i++){ cin >> arr[i]; tot += arr[i]; } dp[0] = 1; for(int i=1;i<=n;i++){ for(int j=250000;j>=arr[i];j--){ dp[j] += dp[j-arr[i]]; } } if(tot%2 or dp[tot/2]==0){ cout << 0 << "\n"; cout << "\n"; return 0; } for(int j=1;j<=n;j++){ for(int i=0;i<=250000;i++){ curr[i] = dp[i]; if(i>=arr[j]){ curr[i] -= curr[i-arr[j]]; } if(curr[i]!=0){ bs[j][i] = true; } } } vector<int> ans; for(int i=1;i<=250000;i++){ bool yes = true; for(int j=1;j<=n;j++){ if((tot-arr[j]+i)%2){ yes = false; break; } int x = (tot-arr[j]+i)/2; if(dp[x]!=0){ yes = false; break; } if(!bs[j][x]){ yes = false; break; } } if(yes){ ans.push_back(i); } } cout << ans.size() << "\n"; for(int i:ans){ cout << i << " "; } 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...