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"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int tmp[200][200],SSZZ;
int opt[201][201];
struct matrix{
int V[200][200];
void friend operator *=(matrix &a,matrix &b){
memcpy(tmp,a.V,sizeof tmp);
for(int i=0;i<SSZZ;i++)
for(int j=0;j<SSZZ;j++)
a.V[i][j]=1e9;
for(int i=0;i<SSZZ;i++)
opt[SSZZ][i]=SSZZ-1;
for(int i=SSZZ;i--;) {
for(int k=0;k<=opt[i+1][0];k++)
if(a.V[i][0]>tmp[i][k]+b.V[k][0])
a.V[i][0]=tmp[i][k]+b.V[k][0],opt[i][0]=k;
for(int j=1;j<SSZZ;j++)
for(int k=opt[i][j-1];k<=opt[i+1][j];k++)
if(a.V[i][j]>tmp[i][k]+b.V[k][j])
a.V[i][j]=tmp[i][k]+b.V[k][j],opt[i][j]=k;
}
}
void reset(){
for(int i=0;i<200;i++)
memset(V[i],15,sizeof V[i]),V[i][i]=0;
}
} mygod[101],finalstuff;
int ans[200][200],lr[5000][200],dn[5000][200],col,row,SZ=310,blocknum;
void recalcblok(int blok){
mygod[blok].reset();
int end=min(row-1,SZ*blok+SZ);
for(int r=SZ*blok+1;r<=end;r++){
for(int i=0;i<col;i++) {
for(int j=0;j<col;j++)
mygod[blok].V[i][j]+=dn[r-1][j];
for(int j=0;++j<col;)
mygod[blok].V[i][j]=min(mygod[blok].V[i][j],
mygod[blok].V[i][j-1]+lr[r][j-1]);
for(int j=col;--j;)
mygod[blok].V[i][j-1]=min(mygod[blok].V[i][j-1],
mygod[blok].V[i][j]+lr[r][j-1]);
}
}
}
void redofinale(){
int pref[200];
pref[0]=0;
for(int i=1;i<200;i++)
pref[i]=pref[i-1]+lr[0][i-1];
for(int i=0;i<col;i++) for(int j=0;j<col;j++)
finalstuff.V[i][j]=abs(pref[i]-pref[j]);
for(int i=0;i<=blocknum;i++)
finalstuff*=mygod[i];
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
SSZZ=C;
for(int i=0;i<5000;i++)
memcpy(lr[i],H[i],sizeof lr[i]),
memcpy(dn[i],V[i],sizeof dn[i]);
row=R;col=C;
blocknum=(R-2)/SZ;
for(int i=0;i<=blocknum;i++)
recalcblok(i);
redofinale();
}
void changeH(int P, int Q, int W) {
lr[P][Q]=W;
if(P)recalcblok(P/SZ),redofinale();
}
void changeV(int P, int Q, int W) {
memset(ans,-1,sizeof ans);
dn[P][Q]=W;
recalcblok(P/SZ),redofinale();
}
int escape(int V1, int V2) {
return finalstuff.V[V1][V2];
}
Compilation message (stderr)
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | 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... |