Submission #342888

#TimeUsernameProblemLanguageResultExecution timeMemory
342888vonatlusBootfall (IZhO17_bootfall)C++17
28 / 100
1090 ms636 KiB
/// wa #pragma GCC optimize("O3") //#pragma comment(linker, "/STACK:36777216") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() #define all(z) (z).begin(), (z).end() using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9 + 7; const int INF = 1e9 + 1e2; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void fin() { #ifdef AM freopen(".in", "r", stdin); #endif } const bool flag = 0; const int N = 1e5+10; const int B = 3e5; bitset<B> dp, tmp; int cnt[B]; void ma1n() { int n; cin >> n; vector<int> a(n); int s = 0, mx = 0; for (int& x : a) { cin >> x, s += x; mx = max(mx, x); } for (int i = -1; i < n; ++i) { dp.reset(); dp.set(s, 1); for (int j = 0; j < n; ++j) { if (i == j) continue; int x = a[j]; for (int b = 0; b <= s*2; ++b) { if (dp[b]) { int d = b+x; if (d <= s*2) tmp[d] = 1; d = b-x; if (d >= 0) tmp[d] = 1; } } dp = tmp; tmp.reset(); } if (i == -1 && !dp[s]) cout << 0, exit(0); for (int b = 0; b <= s; ++b) { if (dp[b]) { cnt[s-b]++; } } } vector<int> ans; for (int i = 0; i <= s; ++i) { if (cnt[i] == n) { ans.pb(i); } } cout << sz(ans) << "\n"; for (int x : ans) cout << x << " "; } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr), fin(); int ts = 1; if (flag) { cin >> ts; } while (ts--) { ma1n(); } 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...