/*input
1 5
0 0 6
*/
#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 rng(0);
const int mxdel = 100000;
ll A_[2 * 300 + 1];
ll ej[2][2 * mxdel + 1];
ll sum[300 + 2];
ll C_[2 * 300 + 1];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int M;
ll L;
cin >> M >> L;
ll* A = A_ + M;
for (ll i = -M; i <= M; i++)
cin >> A[i];
L = -L;
ll cnt = 0;
for (ll l = -M; l <= M; l++)
{
L += l * A[l];
cnt += A[l];
}
A[0] = 0;
ll L_ = L;
ll* C = C_ + M;
C[0] = 0;
for (ll x = M; x >= 1; x--)
{
for (ll v : {x, -x})
{
C[v] = L_ / v;
C[v] = max(ll(0), C[v]);
C[v] = min(ll(A[v]), C[v]);
L_ -= C[v] * v;
}
sum[x] = (ll)roundl(L_);
}
sum[0] = 0;
sum[M + 1] = L;
ll infi = 2e18;
for (ll b = 0; b <= 2 * mxdel; b++)
ej[(M + 1) % 2][b] = infi;
ej[(M + 1) % 2][0 + mxdel] = 0;
for (int x = M; x >= 0; x--)
{
int x1 = (x + 1) % 2;
int x0 = x % 2;
for (int b = 0; b <= 2 * mxdel; b++)
ej[x0][b] = infi;
for (int a = -mxdel; a <= mxdel; a++)
{
ll val = sum[x + 1] + a - sum[x];
ll e = ej[x1][a + mxdel];
if (e != infi)
for (ll v : {x, -x})
{
ll opt = 0;
if (x != 0)
opt = val / v;
opt = max(opt, 0ll);
opt = min(opt, A[v]);
for (ll k = max(0ll, opt - x); k <= min(A[v], opt); k++)
{
ll val_ = val - k * v;
ll e_ = e + k;
if (abs(val_) <= mxdel)
{
if (e_ < ej[x0][val_ + mxdel])
{
ej[x0][val_ + mxdel] = e_;
}
}
}
}
}
}
ll best = ej[0][mxdel];
if (best != infi)
cout << cnt - best << "\n";
else
cout << "impossible\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3412 KB |
Output is correct |
2 |
Correct |
3 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
4 ms |
3412 KB |
Output is correct |
5 |
Correct |
48 ms |
3412 KB |
Output is correct |
6 |
Correct |
12 ms |
3412 KB |
Output is correct |
7 |
Correct |
26 ms |
3412 KB |
Output is correct |
8 |
Correct |
57 ms |
3412 KB |
Output is correct |
9 |
Correct |
94 ms |
3412 KB |
Output is correct |
10 |
Incorrect |
12 ms |
3412 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3412 KB |
Output is correct |
2 |
Correct |
3 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
4 ms |
3412 KB |
Output is correct |
5 |
Correct |
48 ms |
3412 KB |
Output is correct |
6 |
Correct |
12 ms |
3412 KB |
Output is correct |
7 |
Correct |
26 ms |
3412 KB |
Output is correct |
8 |
Correct |
57 ms |
3412 KB |
Output is correct |
9 |
Correct |
94 ms |
3412 KB |
Output is correct |
10 |
Incorrect |
12 ms |
3412 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
8 ms |
3412 KB |
Output is correct |
3 |
Correct |
8 ms |
3412 KB |
Output is correct |
4 |
Correct |
11 ms |
3412 KB |
Output is correct |
5 |
Correct |
9 ms |
3464 KB |
Output is correct |
6 |
Correct |
11 ms |
3348 KB |
Output is correct |
7 |
Incorrect |
8 ms |
3468 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
8 ms |
3412 KB |
Output is correct |
3 |
Correct |
8 ms |
3412 KB |
Output is correct |
4 |
Correct |
11 ms |
3412 KB |
Output is correct |
5 |
Correct |
9 ms |
3464 KB |
Output is correct |
6 |
Correct |
11 ms |
3348 KB |
Output is correct |
7 |
Incorrect |
8 ms |
3468 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
8 ms |
3412 KB |
Output is correct |
3 |
Correct |
8 ms |
3412 KB |
Output is correct |
4 |
Correct |
11 ms |
3412 KB |
Output is correct |
5 |
Correct |
9 ms |
3464 KB |
Output is correct |
6 |
Correct |
11 ms |
3348 KB |
Output is correct |
7 |
Incorrect |
8 ms |
3468 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3412 KB |
Output is correct |
2 |
Correct |
3 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
4 ms |
3412 KB |
Output is correct |
5 |
Correct |
48 ms |
3412 KB |
Output is correct |
6 |
Correct |
12 ms |
3412 KB |
Output is correct |
7 |
Correct |
26 ms |
3412 KB |
Output is correct |
8 |
Correct |
57 ms |
3412 KB |
Output is correct |
9 |
Correct |
94 ms |
3412 KB |
Output is correct |
10 |
Incorrect |
12 ms |
3412 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
8 ms |
3412 KB |
Output is correct |
3 |
Correct |
8 ms |
3412 KB |
Output is correct |
4 |
Correct |
11 ms |
3412 KB |
Output is correct |
5 |
Correct |
9 ms |
3464 KB |
Output is correct |
6 |
Correct |
11 ms |
3348 KB |
Output is correct |
7 |
Incorrect |
8 ms |
3468 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3412 KB |
Output is correct |
2 |
Correct |
3 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
4 ms |
3412 KB |
Output is correct |
5 |
Correct |
48 ms |
3412 KB |
Output is correct |
6 |
Correct |
12 ms |
3412 KB |
Output is correct |
7 |
Correct |
26 ms |
3412 KB |
Output is correct |
8 |
Correct |
57 ms |
3412 KB |
Output is correct |
9 |
Correct |
94 ms |
3412 KB |
Output is correct |
10 |
Incorrect |
12 ms |
3412 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
8 ms |
3412 KB |
Output is correct |
3 |
Correct |
8 ms |
3412 KB |
Output is correct |
4 |
Correct |
11 ms |
3412 KB |
Output is correct |
5 |
Correct |
9 ms |
3464 KB |
Output is correct |
6 |
Correct |
11 ms |
3348 KB |
Output is correct |
7 |
Incorrect |
8 ms |
3468 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3412 KB |
Output is correct |
2 |
Correct |
3 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
4 ms |
3412 KB |
Output is correct |
5 |
Correct |
48 ms |
3412 KB |
Output is correct |
6 |
Correct |
12 ms |
3412 KB |
Output is correct |
7 |
Correct |
26 ms |
3412 KB |
Output is correct |
8 |
Correct |
57 ms |
3412 KB |
Output is correct |
9 |
Correct |
94 ms |
3412 KB |
Output is correct |
10 |
Incorrect |
12 ms |
3412 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |