#include <bits/stdc++.h>
//#include "wombats.h"
#define ent '\n'
using namespace std;
typedef long long ll;
struct asd{
int l, r, t[202][202], opt[202][202];
asd(){
l = r = 0;
for(int i=0;i<202;i++){
for(int j=0;j<202;j++){
opt[i][j] = 200;
t[i][j] = 1e9;
}
}
}
};
int h[5050][205], v[5050][205];
int dp[5050][205];
int n, m, k, N;
asd merge(asd a, asd b){
asd ans;
ans.l = a.l, ans.r = b.r;
for(int i = 0; i < m; i++){
for(int j = m - 1; j >= 0; j--){
int l = 0, r = min(ans.opt[i][j+1], m - 1);
if(i > 0) l = ans.opt[i-1][j];
for(int k = l; k <= r; k++){
int val = a.t[i][k] + b.t[k][j] + v[a.r][k];
if(val < ans.t[i][j]){
ans.t[i][j] = val;
ans.opt[i][j] = k;
}
}
}
}
return ans;
}
asd calc(int l, int r){
asd ans;
ans.l = l, ans.r = r;
for(int x=0;x<m;x++){
for(int i=l;i<=r;i++){
for(int j=0;j<m;j++)
dp[i][j] = 1e9;
}
dp[l][x] = 0;
for(int i=l;i<r;i++){
for(int j=m-2;j>=0;j--){
dp[i][j] = min(dp[i][j], dp[i][j+1] + h[i][j]);
}
for(int j=1;j<m;j++){
dp[i][j] = min(dp[i][j], dp[i][j-1] + h[i][j-1]);
}
for(int j=0;j<m;j++){
dp[i+1][j] = dp[i][j] + v[i][j];
}
}
for(int j=m-2;j>=0;j--){
dp[r][j] = min(dp[r][j], dp[r][j+1] + h[r][j]);
}
for(int j=1;j<m;j++){
dp[r][j] = min(dp[r][j], dp[r][j-1] + h[r][j-1]);
}
for(int y=0;y<m;y++){
ans.t[x][y] = dp[r][y];
}
}
return ans;
}
asd t[250], a[66];
void build(int v, int tl, int tr){
if(tl == tr){
t[v] = a[tl];
}
else{
int mid = tl + tr >> 1;
build(v*2, tl, mid);
build(v*2+1, mid+1, tr);
if(v != 1) t[v] = merge(t[v*2], t[v*2+1]);
}
}
void upd(int v, int tl , int tr, int pos){
if(tl == tr){
t[v] = a[pos];
}
else{
int mid = tl + tr >> 1;
if(pos <= mid){
upd(v*2, tl, mid, pos);
}
else{
upd(v*2+1, mid+1, tr, pos);
}
if(v != 1) t[v] = merge(t[v*2], t[v*2+1]);
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
n = R, m = C;
for(int i=0;i<n;i++){
for(int j=0;j<m-1;j++){
h[i][j] = H[i][j];
}
}
for(int i=0;i<n-1;i++){
for(int j=0;j<m;j++){
v[i][j] = V[i][j];
}
}
k = 83;
for(int i=0;i<n;i+=k){
int j = min(i + k - 1, n - 1);
a[i / k] = calc(i, j);
N = i / k;
}
build(1, 0 , N);
}
void changeH(int i, int j, int x){
h[i][j] = x;
a[i / k] = calc(i / k * k, min(n, (i + k) / k * k) - 1);
upd(1, 0, N, i / k);
}
void changeV(int i, int j, int x){
v[i][j] = x;
a[i / k] = calc(i / k * k, min(n, (i + k) / k * k) - 1);
upd(1, 0, N, i / k);
}
int escape(int vv, int u){
if(N == 0) return a[0].t[vv][u];
int ans = 1e9;
for(int i=0;i<m;i++){
ans = min(ans, t[2].t[vv][i] + t[3].t[i][u] + v[t[2].r][i]);
}
return ans;
}
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 build(int, int, int)':
wombats.cpp:84:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid = tl + tr >> 1;
| ~~~^~~~
wombats.cpp: In function 'void upd(int, int, int, int)':
wombats.cpp:96:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int mid = tl + tr >> 1;
| ~~~^~~~
/usr/bin/ld: /tmp/ccSVliQR.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
