#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 7;
const int M = 200 + 7;
const int INF = (int) 1e9 + 7;
int H[N][M];
int V[N][M];
int n;
int m;
struct Node {
int l;
int r;
Node* lft;
Node* rgh;
int cost[M][M];
Node() :
l(),
r(0),
lft(nullptr),
rgh(nullptr) {
for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) cost[i][j] = INF;
}
};
Node* getSmall(int l, int r) {
assert(l <= r);
Node* solution = new Node;
solution->l = l;
solution->r = r;
for (int start = 0; start < m; start++) {
solution->cost[start][start] = 0;
for (int col = 1; col < m; col++) {
solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col - 1] + H[l][col - 1]);
}
for (int col = m - 2; col >= 0; col--){
solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col + 1] + H[l][col]);
}
}
for (int row = l + 1; row <= r; row++) {
/// add row j
for (int start = 0; start < m; start++) {
for (int col = 0; col < m; col++) {
solution->cost[start][col] += V[row - 1][col];
}
for (int col = 1; col < m; col++) {
solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col - 1] + H[row][col - 1]);
}
for (int col = m - 2; col >= 0; col--){
solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col + 1] + H[row][col]);
}
}
}
return solution;
}
int A[M][M];
int B[M][M];
Node* join(Node* lft, Node* rgh) {
Node* solution = new Node;
solution->l = lft->l;
solution->r = rgh->r;
solution->lft = lft;
solution->rgh = rgh;
assert(lft->r + 1 == rgh->l);
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
A[i][j] = lft->cost[i][j] + V[lft->r][j];
B[i][j] = rgh->cost[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
solution->cost[i][k] = min(solution->cost[i][k], A[i][j] + B[j][k]);
}
}
}
return solution;
}
const int SMALL_LEN = 10;
Node* update(Node* node, int pos) {
if (node->r < pos || pos < node->l) assert(0);
int LEN = node->r - node->l + 1;
if (LEN <= SMALL_LEN) {
return getSmall(node->l, node->r);
} else {
int m = (node->l + node->r) / 2;
if (pos <= m) {
return join(update(node->lft, pos), node->rgh);
} else {
return join(node->lft, update(node->rgh, pos));
}
}
}
Node* build(int l, int r) {
int LEN = r - l + 1;
if (LEN <= SMALL_LEN) {
return getSmall(l, r);
} else {
int m = (l + r) / 2;
return join(build(l, m), build(m + 1, r));
}
}
Node* root;
void print(Node* guy) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
cout << guy->cost[i][j] << " ";
}
cout << "\n";
}
}
void init(int R, int C, int Hinit[5000][200], int Vinit[5000][200]) {
n = R;
m = C;
root = new Node;
root->l = 1;
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) H[i][j] = Hinit[i][j], V[i][j] = Vinit[i][j];
if (0) {
Node* guy01 = getSmall(0, 1);
Node* a = getSmall(0, 0);
Node* b = getSmall(1, 1);
Node* ret = join(a, b);
cout << "expected:\n"; print(guy01);
cout << "a:\n"; print(a);
cout << "b:\n"; print(b);
cout << "ret:\n"; print(ret);
exit(0);
}
root = build(0, n - 1);
/* ... */
}
void changeH(int P, int Q, int W) {
/* ... */
H[P][Q] = W;
root = update(root, P);
}
void changeV(int P, int Q, int W) {
/* ... */
V[P][Q] = W;
root = update(root, P);
}
int escape(int V1, int V2) {
return root->cost[V1][V2];
}
