# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527888 | rainboy | 코알라 (JOI13_koala) | C11 | 30 ms | 1784 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#define N 100000
#define SMALL 1010
#define D 100
#define INF 0x3f3f3f3f3f3f3f3fLL
long long max(long long a, long long b) { return a > b ? a : b; }
int main() {
static int xx[N + 2], bb[N + 2];
static long long dp[N + 2], dq[D];
int n, xl, xr, d, a, i, j, r;
scanf("%d%d%d%d%d", &xl, &xr, &d, &a, &n);
xx[0] = xl;
for (i = 1; i <= n; i++)
scanf("%d%d", &xx[i], &bb[i]);
xx[n + 1] = xr;
n += 2;
if (n <= SMALL) {
dp[0] = 0;
for (j = 1; j < n; j++) {
dp[j] = -INF;
for (i = 0; i < j; i++)
dp[j] = max(dp[j], dp[i] - (long long) (xx[j] - xx[i] + d - 1) / d * a + bb[j]);
}
} else if (d <= D) {
for (r = 0; r < d; r++)
dq[r] = -INF;
for (j = 0; j < n; j++) {
if (j == 0)
dp[j] = 0;
else {
dp[j] = -INF;
for (r = 0; r < d; r++)
dp[j] = max(dp[j], dq[r] - (r < xx[j] % d ? a : 0));
dp[j] += bb[j];
}
dq[xx[j] % d] = max(dq[xx[j] % d], dp[j]);
}
dp[j] -= (long long) (xx[n - 1] / d - xx[0] / d) * a;
} else {
printf(":(\n");
return 0;
}
printf("%lld\n", dp[n - 1]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |