#include <stdio.h>
const int N=5050;
const int M=2048;
const int H=205;
const int inf=1e9+7;
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
int n,m,dp[M][H][H],ls[M],rs[M],x[N][M],y[N][M],tsz,root,opt[H];
void Take(int c)
{
int i,j,k,l,r;
for(i=0;i<m;i++) opt[i]=0;
for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]=inf;
for(i=m-1;i>-m;i--)
{
for(j=min(m-1,m-i-1);j+min(i,0)>=0;j--)
{
if(j==max(-i,0)) l=0;
else l=opt[j-1];
if(j==min(m-1,m-i-1)) r=m-1;
else r=opt[j];
for(k=l;k<=r;k++)
{
if(dp[c][j][j+i]>dp[ls[c]][j][k]+dp[rs[c]][k][j+i])
{
dp[c][j][j+i]=dp[ls[c]][j][k]+dp[rs[c]][k][j+i];
opt[j]=k;
}
}
}
}
}
void Make(int c, int ss, int se)
{
int i,j,k;
for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]=inf;
for(i=0;i<m;i++) dp[c][i][i]=0;
for(k=ss;k<=se;k++)
{
for(i=0;i<m;i++)
{
for(j=1;j<m;j++) dp[c][i][j]=min(dp[c][i][j],dp[c][i][j-1]+x[k][j-1]);
for(j=m-2;~j;j--) dp[c][i][j]=min(dp[c][i][j],dp[c][i][j+1]+x[k][j]);
}
for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]+=y[k][j];
}
}
void Build(int &c, int ss, int se)
{
c=++tsz;
if(se-ss+1<=10)
{
Make(c,ss,se);
return;
}
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
Take(c);
}
void Upd(int c, int ss, int se, int qi)
{
if(se-ss+1<=10)
{
Make(c,ss,se);
return;
}
int mid=ss+se>>1;
if(qi<=mid) Upd(ls[c],ss,mid,qi);
else Upd(rs[c],mid+1,se,qi);
Take(c);
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
n=R;m=C;
int i,j;
for(i=0;i<n;i++) for(j=0;j<m-1;j++) x[i][j]=H[i][j];
for(i=0;i<n-1;i++) for(j=0;j<m;j++) y[i][j]=V[i][j];
Build(root,0,n-1);
}
void changeH(int p, int q, int w){ x[p][q]=w;Upd(root,0,n-1,p);}
void changeV(int p, int q, int w){ y[p][q]=w;Upd(root,0,n-1,p);}
int escape(int a, int b){ return dp[root][a][b];}
//------------------//
/*
int _V[5000][200],_H[5000][200];
int main()
{
int R,C,i,j,Q,p,q,w,a,b,t;
scanf("%i %i",&R,&C);
for(i=0;i<R;i++) for(j=0;j<C-1;j++) scanf("%i",&_H[i][j]);
for(i=0;i<R-1;i++) for(j=0;j<C;j++) scanf("%i",&_V[i][j]);
init(R,C,_H,_V);
scanf("%i",&Q);
while(Q--)
{
scanf("%i",&t);
if(t==1)
{
scanf("%i %i %i",&p,&q,&w);
changeH(p,q,w);
}
if(t==2)
{
scanf("%i %i %i",&p,&q,&w);
changeV(p,q,w);
}
if(t==3)
{
scanf("%i %i",&a,&b);
printf("%i\n",escape(a,b));
}
}
return 0;
}
*/
//------------------//
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
wombats.cpp: In function 'void Build(int&, int, int)':
wombats.cpp:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
wombats.cpp: In function 'void Upd(int, int, int, int)':
wombats.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
/tmp/ccZ6pX4P.o: In function `main':
grader.c:(.text.startup+0x103): undefined reference to `init'
grader.c:(.text.startup+0x164): undefined reference to `escape'
grader.c:(.text.startup+0x1cf): undefined reference to `changeH'
grader.c:(.text.startup+0x23b): undefined reference to `changeV'
collect2: error: ld returned 1 exit status
