#include "wombats.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const ll N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
int R, C, hor[5000][200], ver[5000][200], bl = 10 dp[5000][200];
int Rbl;
struct cut {
vector<vector<ll>> d;
cut() {
for (int i = 0; i < C; i++)
d.push_back(vector<ll>(C, INF));
}
cut(int pos) {
for (int i = 0; i < C; i++) {
d.push_back(vector<ll>(C));
}
int st = bl * pos, en = min(R, bl * (pos + 1));
for (int k = 0; k < C; k++) {
dp[st][k] = 0;
for (int i = k + 1; i < C; i++)
dp[st][i] = dp[st][i-1] + hor[st][i-1];
for (int i = k - 1; i >= 0; i--)
dp[st][i] = dp[st][i+1] + hor[st][i];
for (int i = st + 1; i < en; i++) {
for (int j = 0; j < C; j++) {
dp[i][j] = dp[i-1][j] + ver[i-1][j];
}
for (int j = 1; j < C; j++)
dp[i][j] = min(dp[i][j], dp[i][j-1] + hor[i][j-1]);
for (int j = C - 2; j >= 0; j--)
dp[i][j] = min(dp[i][j], dp[i][j+1] + hor[i][j]);
}
for (int i = 0; i < C; i++)
d[k][i] = dp[en - 1][i];
}
/*cout << "Create on " << pos << endl;
for (int i = 0; i < C; i++) {
for (int j = 0; j < C; j++) {
cout << d[i][j] << ' ';
}
cout << endl;
}*/
}
vector<ll>& operator[](int x) {
return d[x];
}
};
cut merge(cut dl, cut dr, int pos) {
cut d;
pos = bl * (pos + 1) - 1;
/*vector<int> opt(C, -1), optr(C, -1);
for (int i = 0; i < C; i++) {
for (int j = 0; j < C; j++) {
if (d[i][i] > dl[i][j] + ver[pos][j] + dr[j][i]) {
optr[i] = opt[i] = j;
d[i][i] = dl[i][j] + ver[pos][j] + dr[j][i];
}
}
}
for (int k = 1; k < C; k++) {
for (int i = 0; i + k < C; i++) {
for (int j = opt[i]; j <= opt[i+1]; j++) {
if (d[i][i+k] > dl[i][j] + ver[pos][j] + dr[j][i+k]) {
opt[i] = j;
d[i][i+k] = dl[i][j] + ver[pos][j] + dr[j][i+k];
}
}
}
for (int i = C - k - 1; i >= 0; i--) {
int r = optr[i+k];
for (int j = optr[i+k-1]; j <= r; j++) {
if (d[i+k][i] > dl[i+k][j] + ver[pos][j] + dr[j][i]) {
optr[i+k] = j;
d[i+k][i] = dl[i+k][j] + ver[pos][j] + dr[j][i];
}
}
}
}*/
for (int i = 0; i < C; i++) {
for (int j = 0; j < C; j++) {
for (int k = 0; k < C; k++) {
d[i][j] = min(d[i][j], dl[i][k] + ver[pos][k] + dr[k][j]);
}
}
}
/*cout << "Merge on " << pos << endl;
for (int i = 0; i < C; i++) {
cout << ver[pos][i] << endl;
}
for (int i = 0; i < C; i++) {
for (int j = 0; j < C; j++) {
cout << d[i][j] << ' ';
}
cout << endl;
}*/
return d;
}
struct DynamicGrid {
int start;
vector<cut> t;
void build() {
start = 1;
while (start < Rbl) start <<= 1;
t.resize(2 * start);
build(1, 0, start - 1, Rbl);
}
void build(int node, int tl, int tr, int sz) {
if (sz <= tl || tl == tr) {
t[node] = cut(tl);
return;
}
int tm = (tl + tr) / 2;
build(2 * node, tl, tm, sz);
build(2 * node + 1, tm + 1, tr, sz);
if (sz <= tm + 1) t[node] = t[2 * node];
else t[node] = merge(t[2 * node], t[2 * node + 1], tm);
}
void update(int x) {
update(1, 0, start - 1, x);
}
void update(int node, int tl, int tr, int x) {
if (tl == tr) {
t[node] = cut(x / bl);
return;
}
int tm = (tl + tr) / 2;
if (x <= tm) update(2 * node, tl, tm, x);
else update(2 * node + 1, tm + 1, tr, x);
if (Rbl <= tm + 1) t[node] = t[2 * node];
else t[node] = merge(t[2 * node], t[2 * node + 1], tm);
}
int get(int a, int b) {
//cout << "Get " << t[1][a][b] << endl;
return t[1][a][b];
}
} t;
void init(int r, int c, int H[5000][200], int V[5000][200]) {
R = r, C = c;
Rbl = (R + bl - 1) / bl;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
hor[i][j] = H[i][j];
ver[i][j] = V[i][j];
}
t.build();
}
void changeH(int P, int Q, int W) {
hor[P][Q] = W;
t.update(P / bl);
}
void changeV(int P, int Q, int W) {
ver[P][Q] = W;
t.update(P / bl);
}
int escape(int V1, int V2) {
return t.get(V1, V2);
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
wombats.cpp:16:51: error: expected ',' or ';' before 'dp'
16 | int R, C, hor[5000][200], ver[5000][200], bl = 10 dp[5000][200];
| ^~
wombats.cpp: In constructor 'cut::cut(int)':
wombats.cpp:36:4: error: 'dp' was not declared in this scope; did you mean 'd'?
36 | dp[st][k] = 0;
| ^~
| d
