#include <stdio.h>
#include <string.h>
#define N 100
#define S (N * N * N)
#define N3 30
#define S_ (N3 * N3)
#define INF 0x3f3f3f3f
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
void update(int *dp, int s_,int a, int k, int c) {
static int dq[S * 2 + 1], qu[S * 2 + 1];
int s, r, head, cnt;
if (a > 0) {
for (s = 0; s <= s_; s++)
dq[s] = dp[s] == -INF ? -INF : dp[s] - s / a * c;
for (r = 0; r < a; r++) {
head = cnt = 0;
for (s = r; s <= s_; s += a) {
if (dq[s] != -INF) {
while (cnt && dq[qu[head + cnt - 1]] < dq[s])
cnt--;
qu[head + cnt++] = s;
}
dp[s] = cnt == 0 ? -INF : dq[qu[head]] + s / a * c;
if (cnt && qu[head] == s - a * k)
head++, cnt--;
}
}
} else if (a < 0) {
a = -a;
for (s = 0; s <= s_; s++)
dq[s] = dp[s] == -INF ? -INF : dp[s] + s / a * c;
for (r = 0; r < a; r++) {
head = cnt = 0;
for (s = (s_ - r) / a * a + r; s >= 0; s -= a) {
if (dq[s] != -INF) {
while (cnt && dq[qu[head + cnt - 1]] < dq[s])
cnt--;
qu[head + cnt++] = s;
}
dp[s] = cnt == 0 ? -INF : dq[qu[head]] - s / a * c;
if (cnt && qu[head] == s + a * k)
head++, cnt--;
}
}
} else {
if (c <= 0)
return;
for (s = 0; s <= s_; s++)
if (dp[s] != -INF)
dp[s] += k * c;
}
}
long long solve(long long *kk, int n, long long s_) {
static int dp[S_ * 2 + 1], dq[N + 1][S_ + 1];
int a, s1, s2;
long long s, s0, k, k0, ans;
for (s = 0; s <= S_; s++)
dp[s] = -INF;
dp[0] = 0;
for (a = n; a >= 0; a--) {
memcpy(dq[a], dp, (S_ + 1) * sizeof *dp);
update(dp, S_, a, min(kk[a + n], n), 1);
}
for (s = 0; s <= S_ * 2; s++)
dp[s] = -INF;
dp[S_ + 0] = 0;
s0 = 0, k0 = 0;
for (a = -n; a < 0; a++) {
update(dp, S_ * 2, a, min(kk[a + n], n), -1);
s0 += kk[a + n] * a, k0 += kk[a + n];
}
ans = -INF;
for (a = 0; a <= n; a++) {
for (s1 = 0; s1 <= S_ * 2; s1++)
if (dp[s1] != -INF)
for (s2 = 0; s2 <= S_; s2++)
if (dq[a][s2] != -INF) {
s = s0 - (s1 - S_) + s2;
if (a == 0) {
if (s == s_)
ans = max(ans, k0 + dp[s1] + dq[a][s2] + kk[a + n]);
} else {
if (s <= s_ && (s_ - s) % a == 0 && (k = (s_ - s) / a) <= kk[a + n])
ans = max(ans, k0 + dp[s1] + dq[a][s2] + k);
}
}
update(dp, S_ * 2, a, min(kk[a + n], n), -1);
s0 += kk[a + n] * a, k0 += kk[a + n];
}
return ans;
}
int main() {
static long long kk[N * 2 + 1];
static int dp[S * 2 + 1], dq[N][S_ + 1];
int n, a, r, s1, s2, subtask2;
long long s, s_, s0, k0, k, ans, tmp;
scanf("%d%lld", &n, &s_);
subtask2 = n <= N;
for (a = -n; a <= n; a++) {
scanf("%lld", &kk[a + n]);
if (kk[a + n] > N)
subtask2 = 0;
}
if (subtask2 && 0) {
if (s_ < -S || s_ > S) {
printf("impossible\n");
return 0;
}
for (s = 0; s <= S * 2; s++)
dp[s] = -INF;
dp[S + 0] = 0;
for (a = -n; a <= n; a++)
update(dp, S * 2, a, kk[a + n], 1);
if (dp[S + s_] == -INF)
printf("impossible\n");
else
printf("%d\n", dp[S + s_]);
} else if (n <= N3) {
ans = -INF;
for (r = 0; r < 2; r++) {
ans = max(ans, solve(kk, n, s_));
s_ = -s_;
for (a = 1; a <= n; a++)
tmp = kk[n - a], kk[n - a] = kk[n + a], kk[n + a] = tmp;
}
if (ans == -INF)
printf("impossible\n");
else
printf("%lld\n", ans);
} else {
for (s = 0; s <= S_; s++)
dp[s] = -INF;
dp[0] = 0;
for (a = n; a >= 0; a--) {
memcpy(dq[a], dp, (S_ + 1) * sizeof *dp);
update(dp, S_, a, min(kk[a + n], n), 1);
}
for (s = 0; s <= S_; s++)
dp[s] = -INF;
dp[0] = 0;
ans = -INF, s0 = 0, k0 = 0;
for (a = 0; a <= n; a++) {
for (s1 = 0; s1 <= S_; s1++)
if (dp[s1] != -INF)
for (s2 = 0; s2 <= S_; s2++)
if (dq[a][s2] != -INF) {
s = s0 - s1 + s2;
if (a == 0) {
if (s == s_)
ans = max(ans, k0 + dp[s1] + dq[a][s2] + kk[a + n]);
} else {
if (s <= s_ && (s_ - s) % a == 0 && (k = (s_ - s) / a) <= kk[a + n])
ans = max(ans, k0 + dp[s1] + dq[a][s2] + k);
}
}
update(dp, S_, a, min(kk[a + n], n), -1);
s0 += kk[a + n] * a, k0 += kk[a + n];
}
if (ans == -INF)
printf("impossible\n");
else
printf("%lld\n", ans);
}
return 0;
}
Compilation message
vault.c: In function 'main':
vault.c:106:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%lld", &n, &s_);
| ^~~~~~~~~~~~~~~~~~~~~~~~
vault.c:109:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%lld", &kk[a + n]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
48 ms |
468 KB |
Output is correct |
6 |
Incorrect |
64 ms |
480 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
48 ms |
468 KB |
Output is correct |
6 |
Incorrect |
64 ms |
480 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
208 ms |
416 KB |
Output is correct |
3 |
Correct |
103 ms |
340 KB |
Output is correct |
4 |
Correct |
105 ms |
412 KB |
Output is correct |
5 |
Correct |
216 ms |
420 KB |
Output is correct |
6 |
Correct |
44 ms |
340 KB |
Output is correct |
7 |
Correct |
12 ms |
432 KB |
Output is correct |
8 |
Correct |
15 ms |
340 KB |
Output is correct |
9 |
Correct |
77 ms |
340 KB |
Output is correct |
10 |
Correct |
135 ms |
416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
208 ms |
416 KB |
Output is correct |
3 |
Correct |
103 ms |
340 KB |
Output is correct |
4 |
Correct |
105 ms |
412 KB |
Output is correct |
5 |
Correct |
216 ms |
420 KB |
Output is correct |
6 |
Correct |
44 ms |
340 KB |
Output is correct |
7 |
Correct |
12 ms |
432 KB |
Output is correct |
8 |
Correct |
15 ms |
340 KB |
Output is correct |
9 |
Correct |
77 ms |
340 KB |
Output is correct |
10 |
Correct |
135 ms |
416 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
216 ms |
420 KB |
Output is correct |
16 |
Correct |
101 ms |
416 KB |
Output is correct |
17 |
Correct |
104 ms |
416 KB |
Output is correct |
18 |
Correct |
225 ms |
416 KB |
Output is correct |
19 |
Correct |
50 ms |
416 KB |
Output is correct |
20 |
Correct |
11 ms |
432 KB |
Output is correct |
21 |
Correct |
15 ms |
340 KB |
Output is correct |
22 |
Correct |
69 ms |
416 KB |
Output is correct |
23 |
Correct |
130 ms |
412 KB |
Output is correct |
24 |
Correct |
917 ms |
420 KB |
Output is correct |
25 |
Correct |
409 ms |
420 KB |
Output is correct |
26 |
Correct |
582 ms |
412 KB |
Output is correct |
27 |
Correct |
896 ms |
412 KB |
Output is correct |
28 |
Correct |
561 ms |
416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
208 ms |
416 KB |
Output is correct |
3 |
Correct |
103 ms |
340 KB |
Output is correct |
4 |
Correct |
105 ms |
412 KB |
Output is correct |
5 |
Correct |
216 ms |
420 KB |
Output is correct |
6 |
Correct |
44 ms |
340 KB |
Output is correct |
7 |
Correct |
12 ms |
432 KB |
Output is correct |
8 |
Correct |
15 ms |
340 KB |
Output is correct |
9 |
Correct |
77 ms |
340 KB |
Output is correct |
10 |
Correct |
135 ms |
416 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
217 ms |
420 KB |
Output is correct |
13 |
Correct |
108 ms |
416 KB |
Output is correct |
14 |
Correct |
110 ms |
340 KB |
Output is correct |
15 |
Correct |
218 ms |
340 KB |
Output is correct |
16 |
Correct |
43 ms |
340 KB |
Output is correct |
17 |
Correct |
12 ms |
432 KB |
Output is correct |
18 |
Correct |
15 ms |
340 KB |
Output is correct |
19 |
Correct |
77 ms |
424 KB |
Output is correct |
20 |
Correct |
136 ms |
412 KB |
Output is correct |
21 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
48 ms |
468 KB |
Output is correct |
6 |
Incorrect |
64 ms |
480 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
208 ms |
416 KB |
Output is correct |
3 |
Correct |
103 ms |
340 KB |
Output is correct |
4 |
Correct |
105 ms |
412 KB |
Output is correct |
5 |
Correct |
216 ms |
420 KB |
Output is correct |
6 |
Correct |
44 ms |
340 KB |
Output is correct |
7 |
Correct |
12 ms |
432 KB |
Output is correct |
8 |
Correct |
15 ms |
340 KB |
Output is correct |
9 |
Correct |
77 ms |
340 KB |
Output is correct |
10 |
Correct |
135 ms |
416 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
217 ms |
420 KB |
Output is correct |
13 |
Correct |
108 ms |
416 KB |
Output is correct |
14 |
Correct |
110 ms |
340 KB |
Output is correct |
15 |
Correct |
218 ms |
340 KB |
Output is correct |
16 |
Correct |
43 ms |
340 KB |
Output is correct |
17 |
Correct |
12 ms |
432 KB |
Output is correct |
18 |
Correct |
15 ms |
340 KB |
Output is correct |
19 |
Correct |
77 ms |
424 KB |
Output is correct |
20 |
Correct |
136 ms |
412 KB |
Output is correct |
21 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
48 ms |
468 KB |
Output is correct |
6 |
Incorrect |
64 ms |
480 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
208 ms |
416 KB |
Output is correct |
3 |
Correct |
103 ms |
340 KB |
Output is correct |
4 |
Correct |
105 ms |
412 KB |
Output is correct |
5 |
Correct |
216 ms |
420 KB |
Output is correct |
6 |
Correct |
44 ms |
340 KB |
Output is correct |
7 |
Correct |
12 ms |
432 KB |
Output is correct |
8 |
Correct |
15 ms |
340 KB |
Output is correct |
9 |
Correct |
77 ms |
340 KB |
Output is correct |
10 |
Correct |
135 ms |
416 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
217 ms |
420 KB |
Output is correct |
13 |
Correct |
108 ms |
416 KB |
Output is correct |
14 |
Correct |
110 ms |
340 KB |
Output is correct |
15 |
Correct |
218 ms |
340 KB |
Output is correct |
16 |
Correct |
43 ms |
340 KB |
Output is correct |
17 |
Correct |
12 ms |
432 KB |
Output is correct |
18 |
Correct |
15 ms |
340 KB |
Output is correct |
19 |
Correct |
77 ms |
424 KB |
Output is correct |
20 |
Correct |
136 ms |
412 KB |
Output is correct |
21 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
48 ms |
468 KB |
Output is correct |
6 |
Incorrect |
64 ms |
480 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |