# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
964599 | aeg | Uplifting Excursion (BOI22_vault) | C++17 | 2505 ms | 8284 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int OFFSET, OFFSET_SUM;
int dp[2][250005];
signed main() {
int n, l;
cin >> n >> l;
vector<int> v(2 * n + 1);
for (auto& i : v) cin >> i;
OFFSET = n, OFFSET_SUM = n * 50 * 50;
if (l > OFFSET_SUM || l < -OFFSET_SUM) {
cout << "impossible";
return 0;
}
for (int i = 0; i <= 2 * OFFSET_SUM; ++i) dp[0][i] = dp[1][i] = -1e9;
dp[1][OFFSET_SUM] = 0;
for (int i = 0; i <= 2 * n; ++i) {
int actual_value = i - OFFSET;
for (int j = 0; j <= OFFSET_SUM * 2; ++j) {
dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1 ^ 1][j]);
for (int k = 1; k <= v[i]; ++k) {
int prev_sum = j - k * actual_value;
if (prev_sum < 0 || prev_sum > OFFSET_SUM * 2) continue;
dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1 ^ 1][prev_sum] + k);
}
}
}
int ans = dp[0][OFFSET_SUM + l];
if (ans <= 0) cout << "impossible";
else cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |