Submission #1026638

#TimeUsernameProblemLanguageResultExecution timeMemory
1026638gygUplifting Excursion (BOI22_vault)C++17
0 / 100
100 ms1036 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int OFFSET = 2e4, INF = 1e9; int n, tar; unordered_map<int, int> t; array<int, 2 * OFFSET + 5> dp; void comp() { fill(dp.begin(), dp.end(), -INF); dp[OFFSET] = 0; for (int x = -n; x <= n; x++) { for (int i = 1; i <= t[x]; i++) { array<int, 2 * OFFSET + 5> old_dp = dp; for (int y = OFFSET; y >= -OFFSET; y--) if (-OFFSET <= y - x && y - x <= OFFSET) dp[y + OFFSET] = max(old_dp[y + OFFSET], old_dp[y - x + OFFSET] + 1); } } } signed main() { // freopen("vault.in", "r", stdin); cin >> n >> tar; if (tar < -OFFSET || tar > OFFSET) { cout << "impossible" << '\n'; exit(0); } for (int i = -n; i <= n; i++) cin >> t[i]; comp(); cout << ((dp[tar + OFFSET] < 0) ? "impossible" : to_string(dp[tar + OFFSET])) << '\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...