Submission #1023542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023542		vjudge1	Wombats (IOI13_wombats)	C++17	76 / 100	11870 ms	22304 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
int tmp[100][100];
struct matrix{
    int V[100][100];
    void friend operator *=(matrix &a,matrix &b){
        memcpy(tmp,a.V,sizeof tmp);
        for(int i=0;i<100;i++)
            for(int j=0;j<100;j++)
                a.V[i][j]=1e9;
        for(int i=0;i<100;i++)
            for(int j=0;j<100;j++) for(int k=0;k<100;k++)
                a.V[i][j]=min(a.V[i][j],tmp[i][k]+b.V[k][j]);
    }
    void reset(){
        for(int i=0;i<100;i++)
            memset(V[i],15,sizeof V[i]),V[i][i]=0;
    }
} mygod[7],finalstuff;
int ans[100][100],lr[5000][100],dn[5000][100],col,row,SZ=720,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[100]; memcpy(pref+1,lr,99*4);
    for(int i=1;i<100;i++) pref[i]+=pref[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]) {
    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();
}
void calcstuff(int strt){
    int dp[100];
    memset(dp,7,sizeof dp);
    dp[strt]=0;
    for(int i=strt;i--;)
        dp[i]=dp[i+1]+lr[0][i];
    for(int i=strt;++i<col;)
        dp[i]=dp[i-1]+lr[0][i-1];
    for(int i=1;i<row;i++){
        for(int j=0;j<col;j++)
            dp[j]+=dn[i-1][j];
        for(int j=col;--j;)
            dp[j-1]=min(dp[j-1],dp[j]+lr[i][j-1]);
        for(int j=0;++j<col;)
            dp[j]=min(dp[j],dp[j-1]+lr[i][j-1]);
    }
    memcpy(ans[strt],dp,sizeof dp);
}
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;
      |      ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24