Submission #1231375

#TimeUsernameProblemLanguageResultExecution timeMemory
1231375omsincoconutUplifting Excursion (BOI22_vault)C++17
0 / 100
1 ms580 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18, BOUND = 2e4+10; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll M, L; cin >> M >> L; if (L+BOUND/2 < 0 || L+BOUND/2 >= BOUND) { cout << "impossible"; return 0; } ll A[2*M+1]; for (ll i = 0; i <= 2*M; i++) cin >> A[i]; ll knap[BOUND]; fill(knap, knap+BOUND, -INF); knap[BOUND/2] = A[0]; // subtract for (ll i = 1; i <= M; i++) { for (ll j = 1; j <= A[M-i]; j++) { for (ll k = 0; k < BOUND-i; k++) { knap[k] = max(knap[k], knap[k+i]+1); } } } // add for (ll i = 1; i <= M; i++) { for (ll j = 1; j <= A[M+i]; j++) { for (ll k = BOUND-1; k >= i; k--) { knap[k] = max(knap[k], knap[k-i]+1); } } } ll val = knap[L+BOUND/2]; if (val < 0) cout << "impossible"; else cout << val; return 0; } /* 2 5 2 3 1 1 4 */ /* 3 5 3 1 0 2 0 0 2 */ /* 1 5 0 0 6 */
#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...