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 <bits/stdc++.h>
using namespace std;
#define INF 1000000001
#define B 10
struct node{
int n,d[200][200];
void ini(int x){
n=x;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)d[i][j]=0;
else d[i][j]=INF;
}
}
}
node plus(node &q){
node res;
res.ini(n);
int a[205][205];
for(int i=n-1;i>-n;i--){
for(int j=max(-i,0);i+j<n&&j<n;j++){
int x,y;
if(j-1>=0)x=a[i+j][j-1];
else x=0;
if(i+j+1<n)y=a[i+j+1][j];
else y=n-1;
for(int k=x;k<=y;k++)if(d[i+j][k]+q.d[k][j]<d[i+j][x]+q.d[x][j])x=k;
a[i+j][j]=x;
res.d[i+j][j]=min(d[i+j][x]+q.d[x][j],INF);
}
}
return res;
}
};
struct SEG{
int n;
node seg[1<<10];
void ini(int x){
n=x;
for(int i=0;i<1<<10;i++)seg[i].ini(n);
}
void up(int a,node &q){
a+=(1<<9)-1;
seg[a]=q;
while(a>0){
a=(a-1)/2;
seg[a]=seg[a*2+1].plus(seg[a*2+2]);
}
}
};
int h[5005][205],w[5005][205],n,m,p[B][205];
SEG s;
node res[B];
void change(int x){
x=x/B;
for(int i=0;i<B&&x*B+i<n;i++)p[i][0]=0,res[i].ini(m);
for(int i=0;i<B&&x*B+i<n;i++)for(int j=1;j<m;j++)p[i][j]=p[i][j-1]+h[x*B+i][j-1];
for(int i=0;i<B&&x*B+i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<m;k++){
res[i].d[j][k]=p[i][max(j,k)]-p[i][min(j,k)]+w[x*B+i][k];
}
}
}
for(int i=1;i<B&&x*B+i<n;i++)res[0]=res[0].plus(res[i]);
s.up(x,res[0]);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n=R,m=C;
s.ini(m);
for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)h[i][j]=H[i][j];
for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)w[i][j]=V[i][j];
for(int i=0;i<n;i++)change(i);
}
void changeH(int a, int b, int x) {
h[a][b]=x;
change(a);
}
void changeV(int a, int b, int x) {
w[a][b]=x;
change(a);
}
int escape(int a, int b) {
return s.seg[0].d[a][b];
}
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... |