Submission #590655

#TimeUsernameProblemLanguageResultExecution timeMemory
590655tutisUplifting Excursion (BOI22_vault)C++17
20 / 100
5050 ms3148 KiB
/*input 1 5 0 0 6 */ #pragma GCC optimize ("O3") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; using ll = long long; using ull = unsigned long long; using ld = long double; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int M; ll L; cin >> M >> L; ll A[2 * M + 1]; for (int i = 0; i <= 2 * M; i++) cin >> A[i]; array<array<pair<ll, ll>, 300>, 301> v; for (int m = 1; m <= M; m++) { for (int k = 0; k < m; k++) v[m][k] = { -3e18, -3e18}; v[m][0] = {0, 0}; } ll ret = -1; for (ll i = 1; i <= M; i++) { auto w = v; for (ll m = M / 2 + 1; m <= M; m++) for (ll k = 0; k < m; k++) { ll x = v[m][k].first; ll mx = (L - x) / i; mx = min(mx, A[i + M]); for (ll c = mx; c >= 0 && c >= mx - M; c--) { ll val = x + i * c; ll cnt = v[m][k].second + c; for (ll md = M / 2 + 1; md <= M; md++) { ll vv = val % md; w[md][vv] = max(w[md][vv], {val, cnt}); } } } v = w; } for (int m = 1; m <= M; m++) for (int k = 0; k < m; k++) if (v[m][k].first == L) ret = max(ret, v[m][k].second); if (ret < 0) cout << "impossible\n"; else cout << ret + A[M] << "\n"; }
#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...