#include <stdio.h>
#include <string.h>
#define N 100
#define S (N * N * N)
#define N_ 30
#define S_ (N_ * N_)
#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 upd(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;
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;
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;
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;
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;
}
}
int main() {
static long long kk[N * 2 + 1];
static int dp[S * 2 + 1], dq[N][S_ + 1];
int n, a, s1, s2, subtask2;
long long s, s_, s0, k0, k, ans;
scanf("%d%lld", &n, &s_);
subtask2 = n <= N && 0;
for (a = -n; a <= n; a++) {
scanf("%lld", &kk[a + n]);
if (kk[a + n] > N)
subtask2 = 0;
}
if (subtask2) {
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++)
upd(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 <= N_) {
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);
upd(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);
}
}
upd(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:65:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d%lld", &n, &s_);
| ^~~~~~~~~~~~~~~~~~~~~~~~
vault.c:68:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%lld", &kk[a + n]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
