#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxr = 5010, maxc = 210;
const int maxblock = sqrt(maxr) + 10;
void precalculate();
int h[maxr][maxc], v[maxr][maxc], dp[maxblock][maxc][maxc];
int r, c, block_size;
struct node
{
int t[maxc][maxc];
node()
{
for (int i = 0; i < maxc; i ++)
for (int j = 0; j < maxc; j ++)
{
t[i][j] = 0;
}
}
};
const int inf = 2e9 + 10;
node tree[4 * maxblock];
int opt[maxc][maxc];
void divide(int &row, int &root, int &i, int left, int right, int optl, int optr)
{
if (left > right)
return;
int mid = (left + right) / 2;
int opt = -1;
for (int k = optl; k <= optr; k ++)
{
int var = tree[root * 2].t[i][k] + tree[root * 2 + 1].t[k][mid] + v[row - 1][k];
if (var < tree[root].t[i][mid])
{
opt = k;
tree[root].t[i][mid] = var;
}
}
divide(row, root, i, left, mid - 1, optl, opt);
divide(row, root, i, mid + 1, right, opt, optr);
}
void unite(int root, int row)
{
for (int i = 0; i < c; i ++)
for (int j = 0; j < c; j ++)
tree[root].t[i][j] = inf;
int var;
for (int i = 0; i < c; i ++)
{
divide(row, root, i, 0, c - 1, 0, c - 1);
/**
for (int j = 0; j < c; j ++)
for (int k = 0; k < c; k ++)
{
var =tree[root * 2].t[i][k] + tree[root * 2 + 1].t[k][j] + v[row - 1][k];
if (var < tree[root].t[i][j])
{
tree[root].t[i][j] = var;
opt[i][j] = k;
}
//tree[root].t[i][j] = min(tree[root].t[i][j], );
}*/
}
/**for (int i = 0; i < c; i ++)
{
for (int j = i + 1; j < c; j ++)
{
assert(opt[i][j] >= opt[i][j - 1]);
}
}*/
}
void get_leaf(int root, int bl)
{
for (int i = 0; i < c; i ++)
for (int j = 0; j < c; j ++)
tree[root].t[i][j] = dp[bl][i][j];
}
void build(int root, int left, int right)
{
if (left == right)
{
get_leaf(root, left);
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
unite(root, (mid + 1) * block_size);
}
void update(int root, int left, int right, int pivot)
{
if (left == right)
{
get_leaf(root, left);
return;
}
int mid = (left + right) / 2;
if (pivot <= mid)
update(root * 2, left, mid, pivot);
else
update(root * 2 + 1, mid + 1, right, pivot);
unite(root, (mid + 1) * block_size);
}
int m;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
/* ... */
block_size = sqrt(R) + 1; /// maybe by 10 ???
r = R;
c = C;
for (int i = 0; i < R - 1; i ++)
for (int j = 0; j < C; j ++)
v[i][j] = V[i][j];
for (int i = 0; i < R; i ++)
for (int j = 0; j < C - 1; j ++)
h[i][j] = H[i][j];
precalculate();
m = (r - 1) / block_size;
build(1, 0, m);
}
int fp[2][maxc];
void fix_row(int i)
{
for (int j = 1; j < c; j ++)
{
fp[i & 1][j] = min(fp[i & 1][j], fp[i & 1][j - 1] + h[i][j - 1]);
}
for (int j = c - 2; j >= 0; j --)
{
fp[i & 1][j] = min(fp[i & 1][j], fp[i & 1][j + 1] + h[i][j]);
}
}
void calc_block(int bl)
{
int st = bl * block_size;
int en = (bl + 1) * block_size - 1;
en = min(en, r - 1);
for (int d = 0; d < c; d ++)
{
for (int j = 0; j < c; j ++)
{
fp[0][j] = fp[1][j] = inf;
}
fp[st & 1][d] = 0;
fix_row(st);
for (int i = st + 1; i <= en; i ++)
{
for (int j = 0; j < c; j ++)
{
fp[i & 1][j] = fp[(i - 1) & 1][j] + v[i - 1][j];
}
fix_row(i);
}
for (int j = 0; j < c; j ++)
{
dp[bl][d][j] = fp[en & 1][j];
}
}
}
void precalculate()
{
for (int bl = 0; bl <= (r - 1) / block_size; bl ++)
{
/// cout << "calc block " << endl;
calc_block(bl);
}
///exit(0);
}
void changeH(int P, int Q, int W) {
/* ... */
h[P][Q] = W;
calc_block(P / block_size);
update(1, 0, m, P / block_size);
}
void changeV(int P, int Q, int W) {
/* ... */
v[P][Q] = W;
calc_block(P / block_size);
update(1, 0, m, P / block_size);
}
int arr[maxc], temp[maxc];
int escape(int V1, int V2)
{
return tree[1].t[V1][V2];
int v1 = V1, v2 = V2;
for (int j = 0; j < c; j ++)
arr[j] = dp[0][v1][j];
for (int bl = 1; bl <= (r - 1) / block_size; bl ++)
{
int t = bl * block_size;
for (int j = 0; j < c; j ++)
{
arr[j] = arr[j] + v[t - 1][j];
}
for (int j = 1; j < c; j ++)
{
arr[j] = min(arr[j], arr[j - 1] + h[t][j - 1]);
}
for (int j = c - 2; j >= 0; j --)
{
arr[j] = min(arr[j], arr[j + 1] + h[t][j]);
}
for (int j = 0; j < c; j ++)
temp[j] = inf;
for (int j = 0; j < c; j ++)
{
for (int d = 0; d < c; d ++)
temp[j] =min(temp[j], arr[d] + dp[bl][d][j]);
}
for (int j = 0; j < c; j ++)
arr[j] = temp[j];
}
return arr[v2];
}
