Submission #246434

#TimeUsernameProblemLanguageResultExecution timeMemory
246434acmBootfall (IZhO17_bootfall)C++17
65 / 100
1081 ms12912 KiB
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #include <ext/rope> #include <random> #include <chrono> #include <ext/pb_ds/assoc_container.hpp> #include <string> #include <bits/functexcept.h> #include <iosfwd> #include <bits/cxxabi_forced.h> #include <bits/functional_hash.h> #pragma push_macro("__SIZEOF_LONG__") #pragma push_macro("__cplusplus") #define __SIZEOF_LONG__ __SIZEOF_LONG_LONG__ #define unsigned unsigned long #define __cplusplus 201102L #define __builtin_popcountl __builtin_popcountll #define __builtin_ctzl __builtin_ctzll #include <bitset> #pragma pop_macro("__cplusplus") #pragma pop_macro("__SIZEOF_LONG__") #undef unsigned #undef __builtin_popcountl #undef __builtin_ctzl #define file "" #define all(x) x.begin(), x.end() #define sc second #define fr first #define pb push_back #define mp make_pair #define pss pair<line*, line*> using namespace std; using namespace __gnu_cxx; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const ll inf = 1e18; const int MOD = 1e9 + 7; const int dx[] = {-1, +1, -2, +2, -2, +2, -1, +1}; const int dy[] = {-2, -2, -1, -1, +1, +1, +2, +2}; int const N = 250001; int const M = 2e6; bitset<N> dp[505]; signed main() { #ifdef Mask freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; int sum = 0; int a[n + 1]; for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i]; for (int del = 0; del <= n; del++) { dp[del][0] = 1; for (int i = 0; i < n; i++) { if (i + 1 == del) continue; dp[del] |= (dp[del] << a[i + 1]); } } vector<int> ans; for (int k = 1; k <= 250000; k++) { bool ok = true; for (int del = 0; del <= n; del++) { int all = sum + k; if (del == 0) all -= k; else all -= a[del]; if (all % 2 == 1) { ok = false; break; } int need = all / 2; if (need > N) { ok = false; break; } if (dp[del][need] == 0) { ok = false; break; } } if (ok == true) ans.pb(k); } cout << ans.size() << endl; for (int to : ans) cout << to << " "; return 0; }

Compilation message (stderr)

bootfall.cpp:16:0: warning: "__SIZEOF_LONG__" redefined
 #define __SIZEOF_LONG__ __SIZEOF_LONG_LONG__
 
<built-in>: note: this is the location of the previous definition
bootfall.cpp:18:0: warning: "__cplusplus" redefined
 #define __cplusplus 201102L
 
<built-in>: note: this is the location of the previous definition
#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...