#include <bits/stdc++.h>
#include "wombats.h"
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 500;
int h[5000][200];
int v[5000][200];
int r, c;
int s;
struct node{
//vector <int> h;
vector <int> w;
vector <vector <int> > cost;
node(){
cost.resize(c);
for(int i = 0; i < c; i++)
cost[i].resize(c);
w.resize(c);
}
node(int c){
cost.resize(c);
for(int i = 0; i < c; i++)
cost[i].resize(c);
w.resize(c);
}
}t[4 * nmax];
node b[nmax];
node merg(node a, node b){
node c;
c.w = b.w;
int n = a.w.size();
c.cost.resize(n);
vector <vector <int> > opt;
opt.resize(n);
for(int i= 0; i < n; i++)
c.cost[i].resize(n), opt[i].resize(n);
for(int i = 0; i < n; i++){
int mn = 1e9 + 1, mni;
for(int j= 0; j < n; j++){
int val = a.cost[n - 1][j] + a.w[j] + b.cost[j][i];
if(val < mn)
mn = val, mni = j;
}
opt[n - 1][i] = mni, c.cost[n - 1][i] = mn;
}
for(int i = n - 2; i >= 0; i--){
int mn = 1e9 + 1,mni;
for(int j = 0; j < n; j++){
int val = a.cost[i][j] + a.w[j] + b.cost[j][0];
if(val < mn)
mn = val, mni = j;
}
opt[i][0] = mni, c.cost[i][0] = mn;
for(int j = 1; j <= n - 1; j++){
int mn = 1e9 + 1, mni = j;
for(int x = opt[i][j - 1]; x <= opt[i + 1][j]; x++){
int val = a.cost[i][x] + a.w[x] + b.cost[x][j];
if(val < mn)
mn = val, mni = x;
}
opt[i][j] = mni, c.cost[i][j] = mn;
}
}
return c;
}
void update(int v, int l, int r, int pos, node a){
if(l > pos || r < pos)
return;
if(l == r){
t[v] = a;
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, a);
update(2 * v + 1, m + 1, r, pos, a);
t[v] = merg(t[2 * v], t[2 * v + 1]);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
/* ... */
r = R, c = C;
for(int i = 0; i < 5000; i++){
for(int j = 0; j < 200; j++)
h[i][j] = H[i][j], v[i][j] = V[i][j];
a[i] = {c};
}
for(int i = 0; i < r; i++){
node a = {c};
for(int j = 0; j < c; j++)
a.w[j] = V[i][j];
for(int x = 0; x < c; x++){
a.cost[x][x] = 0;
for(int y = x + 1; y < c; ++y){
a.cost[x][y] = a.cost[x][y - 1] + H[i][y - 1];
}
for(int y = x - 1; y >= 0; y--)
a.cost[x][y] = a.cost[x][y + 1] + H[i][y];
}
if(i % 10 == 0)
b[i / 10] = a;
else b[i / 10] = merg(b[i / 10], a);
s = i / 10;
}
for(int i = 0; i <= s; i++)
update(1, 0, s, i, b[i]);
}
void update_block(int o){
// b[o] = a[o * 10];
int x = o * 10;
for(int i = x; i < min(r, x + 10); i++){
node a = {c};
for(int j = 0; j < c; j++)
a.w[j] = V[i][j];
for(int x = 0; x < c; x++){
a.cost[x][x] = 0;
for(int y = x + 1; y < c; ++y){
a.cost[x][y] = a.cost[x][y - 1] + H[i][y - 1];
}
for(int y = x - 1; y >= 0; y--)
a.cost[x][y] = a.cost[x][y + 1] + H[i][y];
}
if(i % 10 == 0)
b[i / 10] = a;
else b[i / 10] = merg(b[i / 10], a);
}
update(1, 0, s, o, b[o]);
}
void changeH(int p, int q, int w) {
/* ... */
h[p][q] = w;
for(int i = 0; i < c; i++){
a[p].w[i] = v[p][i];
}
for(int x = 0; x < c; x++){
a[p].cost[x][x] = 0;
for(int y = x + 1; y < c; ++y){
a[p].cost[x][y] = a[p].cost[x][y - 1] + h[p][y - 1];
}
for(int y = x - 1; y >= 0; y--)
a[p].cost[x][y] = a[p].cost[x][y + 1] + h[p][y];
}
update_block(p / 10);
}
void changeV(int p, int q, int w) {
/* ... */
for(int i = 0; i < c; i++){
a[p].w[q] = w;
}
update_block(p / 10);
}
int escape(int V1, int V2) {
return t[1].cost[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: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:95:9: error: 'a' was not declared in this scope
95 | a[i] = {c};
| ^
wombats.cpp: In function 'void update_block(int)':
wombats.cpp:125:22: error: 'V' was not declared in this scope
125 | a.w[j] = V[i][j];
| ^
wombats.cpp:129:51: error: 'H' was not declared in this scope
129 | a.cost[x][y] = a.cost[x][y - 1] + H[i][y - 1];
| ^
wombats.cpp:132:51: error: 'H' was not declared in this scope
132 | a.cost[x][y] = a.cost[x][y + 1] + H[i][y];
| ^
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:146:9: error: 'a' was not declared in this scope
146 | a[p].w[i] = v[p][i];
| ^
wombats.cpp:149:9: error: 'a' was not declared in this scope
149 | a[p].cost[x][x] = 0;
| ^
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:162:9: error: 'a' was not declared in this scope
162 | a[p].w[q] = w;
| ^
