Submission #962151

#TimeUsernameProblemLanguageResultExecution timeMemory
962151CookieBootfall (IZhO17_bootfall)C++14
100 / 100
363 ms3660 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359, prec = 1e-9;; //using u128 = __uint128_t; //const int x[4] = {1, 0, -1, 0}; //const int y[4] = {0, -1, 0, 1}; const ll mod = 1e9 + 7, pr = 31; const int mxn = 3e5 + 5, mxq = 1e5 + 5, sq = 450, mxv = 5e4 + 1; //const int base = (1 <<18); const ll inf = 1e18 + 5, neg = -69420, inf2 = 1e14; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // have fun! // <3; int n; int dp[505 * 505], a[505], cnt[505 * 505]; void add(int &a, int b){ a += b; if(a >= mod)a -= mod; } void sub(int &a, int b){ b = -b + mod; add(a, b); } void addv(int x){ for(int j = 500 * 500; j >= x; j--){ add(dp[j], dp[j - x]); } } void remv(int x){ for(int j = x; j <= 500 * 500; j++){ sub(dp[j], dp[j - x]); } } void solve(){ cin >> n; int tot = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; tot += a[i]; } dp[0] = 1; for(int i = 1; i <= n; i++){ addv(a[i]); } if((tot & 1) || !dp[tot / 2]){ cout << 0; return; } for(int i = 1; i <= n; i++){ remv(a[i]); tot -= a[i]; for(int j = 0; j <= tot / 2; j++){ if(dp[j]){ cnt[tot - 2 * j]++; } } addv(a[i]); tot += a[i]; } vt<int>res; for(int i = 1; i <= tot; i++){ if(cnt[i] == n)res.pb(i); } cout << sz(res) << "\n"; for(auto i: res)cout << i << " "; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("netw.inp", "r", stdin); //freopen("netw.out", "w", stdout) int tt; tt = 1; while(tt--){ solve(); } 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...