#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAX_C= 200;
const int MAX_R = 5000;
const int INF= 1e9;
const int BLOCK_SZ = 50;
const int BLOCK_NB = 101;
struct Step{
vector<vector<int>> tr;
Step(){};
Step(int nbC){
tr.resize(nbC, vector<int> (nbC, INF));
for(int i = 0; i<nbC; i++){
tr[i][i] = 0;
}
}
Step(int nbC, vector<int> lr, vector<int> d){
assert(lr.size() == nbC-1);
assert(d.size() == nbC);
tr.resize(nbC, vector<int> (nbC, 0));
vector<int> prefCost(nbC);
for(int iC = 0; iC<nbC-1; iC++){
prefCost[iC+1] = prefCost[iC] + lr[iC];
}
for(int beginC = 0; beginC<nbC; beginC++){
for(int endC = 0; endC<nbC; endC++){
if(beginC<=endC){
tr[beginC][endC] = prefCost[endC] - prefCost[beginC] + d[endC];
}
else{
tr[beginC][endC] = prefCost[beginC] - prefCost[endC] + d[endC];
}
}
}
}
void display(){
/*for(int i = 0; i<tr.size(); i++){
for(auto e: tr[i]){
cout<<e<<" ";
}
cout<<endl;
}*/
}
};
int nbC;
void mergeBegin(Step &l, Step &r, Step&res, int Begin, int lMid, int rMid, int lEnd, int rEnd){
if(rEnd<lEnd){
return;
}
int splitEnd = (lEnd+rEnd)/2;
int minC= 1e9;
int minMid = (lMid+rMid)/2;
for(int iMid = lMid; iMid<=rMid; iMid++){
if(l.tr[Begin][iMid] + r.tr[iMid][splitEnd] < minC){
minMid= iMid;
minC = l.tr[Begin][iMid] + r.tr[iMid][splitEnd];
}
}
res.tr[Begin][splitEnd] = minC;
mergeBegin(l, r, res, Begin, lMid, minMid, lEnd, splitEnd-1);
mergeBegin(l, r, res, Begin, minMid, rMid, splitEnd+1, rEnd);
}
Step merge(Step& a, Step b){
Step res(nbC);
for(int iBegin = 0; iBegin<nbC; iBegin++){
mergeBegin(a, b, res, iBegin, 0, nbC-1, 0, nbC-1);
}
return res;
}
struct Tree{
int sz = 1;
vector<Step> tr;
Tree(){};
Tree(int l){
while(sz<l){
sz*=2;
}
tr.resize(2*sz, Step(nbC));
}
void upd(int i){
for(i/=2; i>=1; i/=2){
//cerr<<i<<endl;
tr[i] = merge(tr[i*2], tr[i*2+1]);
tr[i].display();
}
}
void set(int id, Step v){
tr[id+sz] = v;
upd(id+sz);
}
};
Tree tr;
Step steps[BLOCK_NB];
vector<int> lr[MAX_R], d[MAX_R];
Step total;
int nbR;
void recalc_block(int i){
steps[i] = Step(nbC);
for(int iR = i*BLOCK_SZ; iR<min((i+1)*BLOCK_SZ, nbR); iR++){
steps[i] = merge(steps[i], Step(nbC, lr[iR], d[iR]));
}
tr.set(i, steps[i]);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
nbC = C;
nbR = R;
tr =Tree(BLOCK_NB);
for(int iR = 0; iR<R; iR++){
lr[iR].resize(C-1);
d[iR].resize(C);
for(int i = 0; i<C-1; i++){
lr[iR][i] = H[iR][i];
}
if(iR<R-1){
for(int i = 0; i<C; i++){
d[iR][i] = V[iR][i];
}
}
else{
for(int i = 0; i<C; i++){
d[iR][i] = 0;
}
}
//steps.push_back(Step(C, lr[iR], d[iR]));
//steps.back().display();
}
for(int i = 0; i<=(nbR)/BLOCK_SZ; i++){
recalc_block(i);
}
}
void changeH(int P, int Q, int W) {
lr[P][Q] = W;
recalc_block(P/BLOCK_SZ);
}
void changeV(int P, int Q, int W) {
d[P][Q] = W;
recalc_block(P/BLOCK_SZ);
}
int escape(int V1, int V2) {
return tr.tr[1].tr[V1][V2];
}
