Submission #574269

#TimeUsernameProblemLanguageResultExecution timeMemory
5742698e7Uplifting Excursion (BOI22_vault)C++17
0 / 100
497 ms17872 KiB
//Challenge: Accepted #include <bits/stdc++.h> using namespace std; #ifdef zisk void debug(){cout << endl;} template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);} template<class T> void pary(T l, T r) { while (l != r) cout << *l << " ", l++; cout << endl; } #else #define debug(...) 0 #define pary(...) 0 #endif #define ll long long #define maxn 1100005 #define pii pair<int, int> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); const int inf = 1<<30; int dp[2][maxn]; int main() { io int m; ll L; cin >> m >> L; vector<ll> a(2*m+1); ll ans = 0; for (int i = 0;i < 2*m+1;i++) cin >> a[i]; for (int i = 0;i < m;i++) { L += a[i] * (m - i); a[2 * m - i] += a[i]; } for (int i = 0;i < maxn;i++) dp[0][i] = dp[1][i] = -inf; dp[0][0] = 0; dp[1][0] = 0; for (int i = m;i < 2*m+1;i++) { ll cnt = 1; vector<int> num; while (a[i] >= cnt) { num.push_back(cnt); a[i] -= cnt; cnt <<= 1; } if (a[i] > 0) num.push_back(a[i]); for (int p:num) { for (int j = 0;j < maxn;j++) { int val = j + p * (i-m); if (val < maxn) dp[1][val] = max(dp[1][val], dp[0][j] + p); } for (int j = 0;j < maxn;j++) dp[0][j] = dp[1][j]; } } if (L >= maxn || L < 0 || dp[0][L] < 0) cout << "impossible\n"; else cout << dp[0][L] << "\n"; }

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:29:5: warning: unused variable 'ans' [-Wunused-variable]
   29 |  ll ans = 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...