This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int OFFSET = 5e5, 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++) {
if (x >= 0) {
for (int y = OFFSET; y >= -OFFSET; y--)
if (-OFFSET <= y - x && y - x <= OFFSET) dp[y + OFFSET] = max(dp[y + OFFSET], dp[y - x + OFFSET] + 1);
} else {
for (int y = -OFFSET; y <= OFFSET; y++)
if (-OFFSET <= y - x && y - x <= OFFSET) dp[y + OFFSET] = max(dp[y + OFFSET], 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 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... |