This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wombats.h"
#include<iostream>
using namespace std;
const int tmw=14;
const int M=5001,N=201,S=1501;
int m,n;
int dp[S][N][N];
int dp2[32][N][N];
int lc[S],rc[S];
int h[M][N],v[M][N];
void cal(int id,int st,int l,int r,int optl,int optr){
if(l>r) return;
int opt=0,mid=(l+r)/2;
dp[id][st][mid]=1e9;
for(int i=optl; i<=optr ;i++)
if(dp[id][st][mid]>dp[lc[id]][st][i]+dp[rc[id]][i][mid])
dp[id][st][mid]=dp[lc[id]][st][i]+dp[rc[id]][i][mid],opt=i;
cal(id,st,l,mid-1,optl,opt);
cal(id,st,mid+1,r,opt,optr);
}
void cal2(int id,int st,int l,int r,int optl,int optr){
if(l>r) return;
int opt=0,mid=(l+r)/2;
dp2[id][st][mid]=1e9;
for(int i=optl; i<=optr ;i++)
if(dp2[id][st][mid]>dp2[id*2][st][i]+dp2[id*2+1][i][mid])
dp2[id][st][mid]=dp2[id*2][st][i]+dp2[id*2+1][i][mid],opt=i;
cal2(id,st,l,mid-1,optl,opt);
cal2(id,st,mid+1,r,opt,optr);
}
void upd2(int id,int l,int r){
if(l==r){
for(int i=1; i<=n ;i++){
dp2[id][i][i]=v[l][i];
for(int j=i+1; j<=n ;j++)
dp2[id][i][j]=dp2[id][i][j-1]-v[l][j-1]+v[l][j]+h[l][j-1];
for(int j=i-1; j>=1 ;j--)
dp2[id][i][j]=dp2[id][i][j+1]-v[l][j+1]+v[l][j]+h[l][j];
for(int j=1+1; j<=n ;j++) dp2[id][i][j]=min(dp2[id][i][j],dp2[id][i][j-1]+h[l+1][j-1]);
for(int j=n-1; j>=1 ;j--) dp2[id][i][j]=min(dp2[id][i][j],dp2[id][i][j+1]+h[l+1][j]);
//cout << id << ' ' << l << ' ' << i << ": ";
//for(int j=1; j<=n ;j++) cout << dp2[id][i][j] << ' ';
//cout << endl;
}
return;
}
int mid=(l+r)/2;
upd2(id*2,l,mid);upd2(id*2+1,mid+1,r);
for(int i=1; i<=n ;i++) cal2(id,i,1,n,1,n);
}
void upd(int id,int l,int r,int x,int y){
if((l>x || x>r) && (l>y || y>r)) return;
if(r-l<tmw){
upd2(1,l,r);
for(int i=1; i<=n ;i++) for(int j=1; j<=n ;j++) dp[id][i][j]=dp2[1][i][j];
return;
}
int mid=(l+r)/2;
upd(lc[id],l,mid,x,y);
upd(rc[id],mid+1,r,x,y);
for(int i=1; i<=n ;i++) cal(id,i,1,n,1,n);
}
int ptr=1;
void build(int id,int l,int r){
if(r-l<tmw){
upd2(1,l,r);
for(int i=1; i<=n ;i++) for(int j=1; j<=n ;j++) dp[id][i][j]=dp2[1][i][j];
return;
}
lc[id]=++ptr;rc[id]=++ptr;
int mid=(l+r)/2;
build(lc[id],l,mid);build(rc[id],mid+1,r);
for(int i=1; i<=n ;i++) cal(id,i,1,n,1,n);
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
m=R;n=C;
for(int i=0; i<m ;i++)
for(int j=0; j<n ;j++)
h[i+1][j+1]=H[i][j],v[i+1][j+1]=V[i][j];
build(1,1,m-1);
}
void changeH(int P, int Q, int W){
int p=P+1,q=Q+1,w=W;
h[p][q]=w;
upd(1,1,m-1,p-1,p);
}
void changeV(int P, int Q, int W){
int p=P+1,q=Q+1,w=W;
v[p][q]=w;
upd(1,1,m-1,p,p);
}
int escape(int V1, int V2){
int p=V1+1,q=V2+1;
return dp[1][p][q];
}
Compilation message (stderr)
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |