/*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);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll M;
ll L;
cin >> M >> L;
ll A_[2 * M + 1];
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;
ld L_ = L;
ld C_[2 * M + 1];
ld* C = C_ + M;
C[0] = 0;
ll sum[M + 2];
for (ll x = M; x >= 1; x--)
{
for (ll v : {x, -x})
{
C[v] = L_ / v;
C[v] = max(ld(0), C[v]);
C[v] = min(ld(A[v]), C[v]);
L_ -= C[v] * v;
}
sum[x] = (ll)roundl(L_);
}
sum[0] = 0;
sum[M + 1] = L;
const ll mxdel = 10000;
ll infi = 2e18;
ll ej[M + 2][2 * mxdel + 1];
for (ll a = 0; a <= M + 1; a++)
for (ll b = 0; b <= 2 * mxdel; b++)
ej[a][b] = infi;
ej[M + 1][0 + mxdel] = 0;
for (ll x = M; x >= 0; x--)
{
for (ll v : {x, -x})
{
for (ll a = -mxdel; a <= mxdel; a++)
{
ll val = sum[x + 1] + a;
ll e = ej[x + 1][a + mxdel];
if (e == infi)
continue;
for (ll k = 0; k <= A[v]; k++)
{
ll val_ = val - k * v - sum[x];
ll e_ = e + k;
if (abs(val_) <= mxdel)
{
if (e_ < ej[x][val_ + mxdel])
{
ej[x][val_ + mxdel] = e_;
}
}
}
}
}
}
ll best = ej[0][mxdel];
if (best != infi)
cout << cnt - best << "\n";
else
cout << "impossible\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
1032 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
2 ms |
2132 KB |
Output is correct |
5 |
Correct |
44 ms |
8404 KB |
Output is correct |
6 |
Correct |
73 ms |
8404 KB |
Output is correct |
7 |
Correct |
19 ms |
8404 KB |
Output is correct |
8 |
Correct |
55 ms |
8404 KB |
Output is correct |
9 |
Correct |
82 ms |
8436 KB |
Output is correct |
10 |
Correct |
6 ms |
8404 KB |
Output is correct |
11 |
Correct |
7 ms |
8404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
1032 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
2 ms |
2132 KB |
Output is correct |
5 |
Correct |
44 ms |
8404 KB |
Output is correct |
6 |
Correct |
73 ms |
8404 KB |
Output is correct |
7 |
Correct |
19 ms |
8404 KB |
Output is correct |
8 |
Correct |
55 ms |
8404 KB |
Output is correct |
9 |
Correct |
82 ms |
8436 KB |
Output is correct |
10 |
Correct |
6 ms |
8404 KB |
Output is correct |
11 |
Correct |
7 ms |
8404 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
2 ms |
2132 KB |
Output is correct |
16 |
Correct |
40 ms |
8404 KB |
Output is correct |
17 |
Correct |
72 ms |
8436 KB |
Output is correct |
18 |
Correct |
20 ms |
8460 KB |
Output is correct |
19 |
Correct |
58 ms |
8404 KB |
Output is correct |
20 |
Correct |
80 ms |
8436 KB |
Output is correct |
21 |
Correct |
7 ms |
8404 KB |
Output is correct |
22 |
Correct |
7 ms |
8464 KB |
Output is correct |
23 |
Correct |
137 ms |
16276 KB |
Output is correct |
24 |
Correct |
266 ms |
16212 KB |
Output is correct |
25 |
Correct |
55 ms |
16212 KB |
Output is correct |
26 |
Correct |
413 ms |
16268 KB |
Output is correct |
27 |
Correct |
301 ms |
16212 KB |
Output is correct |
28 |
Correct |
18 ms |
16196 KB |
Output is correct |
29 |
Correct |
19 ms |
16340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2132 KB |
Output is correct |
2 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2132 KB |
Output is correct |
2 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2132 KB |
Output is correct |
2 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
1032 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
2 ms |
2132 KB |
Output is correct |
5 |
Correct |
44 ms |
8404 KB |
Output is correct |
6 |
Correct |
73 ms |
8404 KB |
Output is correct |
7 |
Correct |
19 ms |
8404 KB |
Output is correct |
8 |
Correct |
55 ms |
8404 KB |
Output is correct |
9 |
Correct |
82 ms |
8436 KB |
Output is correct |
10 |
Correct |
6 ms |
8404 KB |
Output is correct |
11 |
Correct |
7 ms |
8404 KB |
Output is correct |
12 |
Correct |
2 ms |
2132 KB |
Output is correct |
13 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2132 KB |
Output is correct |
2 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
1032 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
2 ms |
2132 KB |
Output is correct |
5 |
Correct |
44 ms |
8404 KB |
Output is correct |
6 |
Correct |
73 ms |
8404 KB |
Output is correct |
7 |
Correct |
19 ms |
8404 KB |
Output is correct |
8 |
Correct |
55 ms |
8404 KB |
Output is correct |
9 |
Correct |
82 ms |
8436 KB |
Output is correct |
10 |
Correct |
6 ms |
8404 KB |
Output is correct |
11 |
Correct |
7 ms |
8404 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
2 ms |
2132 KB |
Output is correct |
16 |
Correct |
40 ms |
8404 KB |
Output is correct |
17 |
Correct |
72 ms |
8436 KB |
Output is correct |
18 |
Correct |
20 ms |
8460 KB |
Output is correct |
19 |
Correct |
58 ms |
8404 KB |
Output is correct |
20 |
Correct |
80 ms |
8436 KB |
Output is correct |
21 |
Correct |
7 ms |
8404 KB |
Output is correct |
22 |
Correct |
7 ms |
8464 KB |
Output is correct |
23 |
Correct |
137 ms |
16276 KB |
Output is correct |
24 |
Correct |
266 ms |
16212 KB |
Output is correct |
25 |
Correct |
55 ms |
16212 KB |
Output is correct |
26 |
Correct |
413 ms |
16268 KB |
Output is correct |
27 |
Correct |
301 ms |
16212 KB |
Output is correct |
28 |
Correct |
18 ms |
16196 KB |
Output is correct |
29 |
Correct |
19 ms |
16340 KB |
Output is correct |
30 |
Correct |
2 ms |
2132 KB |
Output is correct |
31 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2132 KB |
Output is correct |
2 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
1032 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
2 ms |
2132 KB |
Output is correct |
5 |
Correct |
44 ms |
8404 KB |
Output is correct |
6 |
Correct |
73 ms |
8404 KB |
Output is correct |
7 |
Correct |
19 ms |
8404 KB |
Output is correct |
8 |
Correct |
55 ms |
8404 KB |
Output is correct |
9 |
Correct |
82 ms |
8436 KB |
Output is correct |
10 |
Correct |
6 ms |
8404 KB |
Output is correct |
11 |
Correct |
7 ms |
8404 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
2 ms |
2132 KB |
Output is correct |
16 |
Correct |
40 ms |
8404 KB |
Output is correct |
17 |
Correct |
72 ms |
8436 KB |
Output is correct |
18 |
Correct |
20 ms |
8460 KB |
Output is correct |
19 |
Correct |
58 ms |
8404 KB |
Output is correct |
20 |
Correct |
80 ms |
8436 KB |
Output is correct |
21 |
Correct |
7 ms |
8404 KB |
Output is correct |
22 |
Correct |
7 ms |
8464 KB |
Output is correct |
23 |
Correct |
137 ms |
16276 KB |
Output is correct |
24 |
Correct |
266 ms |
16212 KB |
Output is correct |
25 |
Correct |
55 ms |
16212 KB |
Output is correct |
26 |
Correct |
413 ms |
16268 KB |
Output is correct |
27 |
Correct |
301 ms |
16212 KB |
Output is correct |
28 |
Correct |
18 ms |
16196 KB |
Output is correct |
29 |
Correct |
19 ms |
16340 KB |
Output is correct |
30 |
Correct |
2 ms |
2132 KB |
Output is correct |
31 |
Execution timed out |
5022 ms |
5204 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |