#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];
asd(){
l = r = 0;
for(int i=0;i<202;i++){
for(int j=0;j<202;j++){
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=0;j<m;j++){
for(int k=0;k<m;k++){
ans.t[i][k] = min(ans.t[i][k], a.t[i][j] + b.t[j][k] + v[a.r][j]);
}
}
}
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[80], a[20];
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 = 313;
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 v, int u){
if(N == 0) return a[0].t[v][u];
int ans = 1e9;
for(int i=0;i<m;i++){
ans = min(ans, t[2].t[v][i] + t[3].t[i][v] + 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:77:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int mid = tl + tr >> 1;
| ~~~^~~~
wombats.cpp: In function 'void upd(int, int, int, int)':
wombats.cpp:89:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int mid = tl + tr >> 1;
| ~~~^~~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:137:55: error: invalid types 'int[int]' for array subscript
137 | ans = min(ans, t[2].t[v][i] + t[3].t[i][v] + v[t[2].r][i]);
| ^
