#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "wombats.h"
#include "grader.h"
using namespace std;
typedef long long int ll;
const int INF = 1e9 + 7;
const int MAXN = 2005;
const double eps = 1e-9;
int RW, C, root = 0, segSz = 1;
int h[5000][200], v[5000][200], L[MAXN], R[MAXN];
int dp[MAXN][200][200], opt[200];
void merge(int cur) {
for (int i = 0; i < C; i++) {
opt[i] = 0;
for (int j = 0; j < C; j++)
dp[cur][i][j] = INF;
}
for (int i = C - 1; i > -C; i--) {
for (int j = C + min(-i, 0) - 1; j >= max(-i, 0); j--) {
int oL = 0, oR = C - 1;
if (j != max(-i, 0))
oL = opt[j - 1];
if (j != C + min(-i, 0) - 1)
oR = opt[j];
for (int k = oL; k <= oR; k++) {
if (dp[cur][j][i + j] > dp[L[cur]][j][k] + dp[R[cur]][k][i + j]) {
dp[cur][j][i + j] = dp[L[cur]][j][k] + dp[R[cur]][k][i + j];
opt[j] = k;
}
}
}
}
}
void init(int cur, int l, int r) {
for (int i = 0; i < C; i++) {
for (int j = 0; j < C; j++)
dp[cur][i][j] = INF;
dp[cur][i][i] = 0;
}
for (int k = l; k <= r; k++) {
for (int i = 0; i < C; i++) {
for (int j = 1; j < C; j++)
dp[cur][i][j] = min(dp[cur][i][j], dp[cur][i][j - 1] + h[k][j - 1]);
for (int j = C - 2; j > -1; j--)
dp[cur][i][j] = min(dp[cur][i][j], dp[cur][i][j + 1] + h[k][j]);
}
for (int i = 0; i < C; i++)
for (int j = 0; j < C; j++)
dp[cur][i][j] += v[k][j];
}
}
void upd(int l, int r, int cur, int ind) {
if (l + 9 >= r) {
init(cur, l, r);
return;
}
int m = (l + r) / 2;
if (ind <= m) upd(l, m, L[cur], ind);
else upd(m + 1, r, R[cur], ind);
merge(cur);
}
void build(int l, int r, int &cur) {
cur = segSz++;
if (l + 9 >= r) {
init(cur, l, r);
return;
}
int m = (l + r) / 2;
build(l, m, L[cur]);
build(m + 1, r, R[cur]);
merge(cur);
}
void init(int R1, int C1, int H[5000][200], int V[5000][200]) {
RW = R1, C = C1;
for (int i = 0; i < RW; i++)
for (int j = 0; j + 1 < C; j++)
h[i][j] = H[i][j];
for (int i = 0; i + 1 < RW; i++)
for (int j = 0; j < C; j++)
v[i][j] = V[i][j];
build(0, RW - 1, root);
}
void changeH(int p, int q, int w) {
h[p][q] = w;
upd(0, RW - 1, root, p);
}
void changeV(int p, int q, int w) {
v[p][q] = w;
upd(0, RW - 1, root, p);
}
int escape(int a, int b) {
return dp[root][a][b];
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
wombats.cpp:4:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
