#pragma once
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
namespace WOMBAT{
ll ans[210];
ll R,C,H[5010][210],V[5010][210];
const ll SZ_TREE = 1024;
const ll INF = 1e9;
ll tree[SZ_TREE][210][210];
ll opt[210][210];
ll dp[210];
void solve(ll id,ll l,ll r){
for (ll st = 0;st < C;st ++){
dp[st] = 0;
for (ll j = st - 1;j >= 0;j --){
dp[j] = dp[j+1] + H[l][j];
}
for (ll j = st + 1;j < C;j ++){
dp[j] = dp[j-1] + H[l][j-1];
}
for (ll j = l + 1;j <= r + 1;j ++){
for (ll k = 0;k < C;k ++){
dp[k] += V[j-1][k];
}
for (ll k = 1;k < C;k ++){
dp[k] = min(dp[k],dp[k-1] + H[j][k-1]);
}
for (ll k = C - 2;k >= 0;k --){
dp[k] = min(dp[k],dp[k+1] + H[j][k]);
}
// for (ll k = 0;k < C;k ++){
// cout<<dp[k]<<' ';
// }
// cout<<'\n';
}
for (ll j = 0;j < C;j ++){
tree[id][st][j] = dp[j];
}
}
}
void reupdate(ll id){
for (ll st = 0;st < C;st ++){
for (ll en = C - 1;en >= 0;en--){
ll optl = (st == 0 ? 0 : opt[st-1][en]);
ll optr = (en == C - 1 ? C - 1 : opt[st][en+1]);
ll optmid = optl;
for (ll j = optl + 1;j <= optr; j++){
if (tree[id<<1][st][j] + tree[id<<1|1][j][en] < tree[id<<1][st][optmid] + tree[id<<1|1][optmid][en]){
optmid = j;
}
}
opt[st][en] = optmid;
tree[id][st][en] = tree[id<<1][st][optmid] + tree[id<<1|1][optmid][en];
}
}
}
void build(ll id,ll l,ll r){
if (l == r || id * 2 + 1 >= SZ_TREE){
solve(id,l,r);
return;
}
ll mid = (l + r) >> 1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
reupdate(id);
}
void update(ll id,ll l,ll r,ll i){
if (l == r || id * 2 + 1 >= SZ_TREE){
solve(id,l,r);
return;
}
ll mid = (l + r) >> 1;
update(id<<1,l,mid,i);
update(id<<1|1,mid+1,r,i);
reupdate(id);
}
}
void init(int R1, int C1, int H1[5000][200], int V1[5000][200]){
using namespace WOMBAT;
R = R1,C = C1;
for (ll i = 0;i < R;i ++){
for (ll j = 0;j < C - 1;j ++){
H[i][j] = H1[i][j];
}
}
for (ll i = 0;i < R - 1;i ++){
for (ll j = 0;j < C;j ++){
V[i][j] = V1[i][j];
}
}
build(1,0,R-2);
}
void changeH(int P, int Q, int W){
using namespace WOMBAT;
H[P][Q] = W;
update(1,0,R-2,P-1);
}
void changeV(int P, int Q, int W){
using namespace WOMBAT;
V[P][Q] = W;
update(1,0,R-2,P);
}
int escape(int V1, int V2){
using namespace WOMBAT;
return tree[1][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:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
/usr/bin/ld: /tmp/ccpADa4d.o: in function `main':
grader.c:(.text.startup+0x129): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0x194): undefined reference to `escape'
/usr/bin/ld: grader.c:(.text.startup+0x203): undefined reference to `changeH'
/usr/bin/ld: grader.c:(.text.startup+0x26d): undefined reference to `changeV'
collect2: error: ld returned 1 exit status
