Submission #857726

#TimeUsernameProblemLanguageResultExecution timeMemory
857726vgtcrossUplifting Excursion (BOI22_vault)C++17
20 / 100
3806 ms9812 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; const int N = 1100000; int dp[N], nx[N]; ll dp2[N], nx2[N]; void solve() { int m; ll x; cin >> m >> x; vector<ll> a(2*m+1); ll maxa = 0; for (ll &i : a) { cin >> i; maxa = max(maxa, i); } if (maxa <= 100) { ll mins = 0, maxs = 0; vector<pii> v; for (int i = -m; i <= m; ++i) { int f = a[i+m]; if (i < 0) mins += f * i; else maxs += f * i; int z = 1; while (f > z) { v.push_back({z * i, z}); f -= z; z *= 2; } if (f > 0) v.push_back({f * i, f}); } memset(dp, 0xc0, sizeof dp); memset(nx, 0xc0, sizeof nx); dp[0] = nx[0] = 0; for (pii p : v) { for (int i = -550000; i <= 550000; ++i) { int j = i + p.first; if (-550000 <= j && j <= 550000) nx[(j + N) % N] = max(nx[(j + N) % N], dp[(i + N) % N] + p.second); } copy(nx, nx+N, dp); } if (x < mins || x > maxs) cout << "impossible\n"; else cout << (dp[(x + N) % N] < 0 ? "impossible" : to_string(dp[(x + N) % N])) << '\n'; } else { ll maxs = 0; vector<pii> v[m+1]; for (int i = 1; i <= m; ++i) { ll f = a[i+m]; maxs += f * i; f = min(f, (ll) m-1); int z = 1; while (f > z) { v[i].push_back({z * i, z}); f -= z; z *= 2; } if (f > 0) v[i].push_back({f * i, f}); } ll ans = -1; ll ofs = 0; for (int k = 1; k <= m; ++k) { memset(dp2, 0xc0, 77000 * sizeof(ll)); memset(nx2, 0xc0, 77000 * sizeof(ll)); dp2[0] = nx2[0] = 0; for (int b = 1; b <= m; ++b) if (b != k) { for (pii p : v[b]) { for (int i = 0; i <= 70000; ++i) { int j = i + p.first; if (j <= 70000) nx2[j] = max(nx2[j], dp2[i] + p.second); } copy(nx2, nx2+77000, dp2); } } for (int i = 0; i <= 70000; ++i) { if (i + ofs > x) break; if ((x - i - ofs) % k == 0) ans = max(ans, dp2[i] + (x - i - ofs) / k); } ofs += max(0ll, a[k+m] - m + 1) * k; } cout << (ans == -1 ? "impossible" : to_string(ans + a[m])) << '\n'; } } int main() { cin.tie(0) -> sync_with_stdio(0); solve(); }
#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...