Submission #937834

#TimeUsernameProblemLanguageResultExecution timeMemory
937834LucaIlieUplifting Excursion (BOI22_vault)C++17
5 / 100
5067 ms5200 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_M = 300; const int MAX_S = 3e5; const int MIN_S = -MAX_S; const long long INF = 1e18; int a[2 * MAX_M + 1]; long long maxObj[MAX_S - MIN_S + 1]; int main() { int m, l; cin >> m >> l; for ( int i = 0; i <= 2 * m; i++ ) cin >> a[i]; for ( int s = 0; s <= MAX_S - MIN_S; s++ ) maxObj[s] = -INF; maxObj[0 - MIN_S] = 0; for ( int i = 0; i <= 2 * m; i++ ) { int x = i - m; for ( int j = 1; j <= a[i] && j * x <= MAX_S && j * x >= MIN_S; j++ ) { if ( x > 0 ) { for ( int s = MAX_S - MIN_S; s >= x; s-- ) maxObj[s] = max( maxObj[s], maxObj[s - x] + 1 ); } else { for ( int s = x; s <= MAX_S - MIN_S; s++ ) maxObj[s] = max( maxObj[s], maxObj[s - x] + 1 ); } } } if ( l < MIN_S || l > MAX_S || maxObj[l - MIN_S] < 0 ) cout << "impossible\n"; else cout << maxObj[l - MIN_S] << "\n"; return 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...