#include "peru.h"
#include <string.h>
#define N 2500000
#define INF 0x3f3f3f3f3f3f3f3fLL
#define MD 1000000007
#define X 23
long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int solve(int n, int k, int *aa) {
static int qq[N + 1], pp[N + 1], qu[N + 1];
static long long dp[N + 1], dq[N + 1];
int cnt, i, j, l, r, ans;
long long x;
memset(dp, 0x3f, (n + 1) * sizeof *dp), dp[0] = 0;
for (l = 0; l <= n; l += k) {
r = min(l + k, n + 1);
if (l >= k) {
qq[l] = 0;
for (i = l - 1; i >= l - k; i--)
qq[i] = max(qq[i + 1], aa[i]);
pp[l] = 0;
for (i = l; i < r; i++)
pp[i + 1] = max(pp[i], aa[i]);
for (j = r - 1, i = j - k, x = INF; j >= l; j--) {
if (j - k >= 0 && i > j - k) {
if (qq[j - k] >= pp[j])
x = min(x, dp[j - k] + qq[j - k]);
else
i = j - k;
}
while (i < l && qq[i] >= pp[j])
x = min(x, dp[i] + qq[i]), i++;
dp[j] = min(x, i == l ? INF : dp[i] + pp[j]);
}
}
cnt = 0;
for (i = l; i < r; i++) {
if (cnt)
dp[i] = min(dp[i], dq[cnt - 1]);
if (i < r) {
while (cnt && aa[qu[cnt - 1]] <= aa[i])
cnt--;
qu[cnt] = i, dq[cnt] = cnt == 0 ? dp[l] + aa[i] : min(dq[cnt - 1], dp[qu[cnt - 1] + 1] + aa[i]), cnt++;
}
}
}
ans = 0;
for (i = 1; i <= n; i++)
ans = ((long long) ans * X + dp[i] % MD) % MD;
return ans;
}
Compilation message
grader.c:1:10: fatal error: cstdio: No such file or directory
1 | #include <cstdio>
| ^~~~~~~~
compilation terminated.
