oj.uz

답안 #1023846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1023846 2024-07-15T07:49:14 Z vjudge1 웜뱃 (IOI13_wombats) C++17
37 / 100
 1174 ms 21588 KB 
#include "wombats.h"
#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;
        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[51],finalstuff;
int ans[200][200],lr[5000][200],dn[5000][200],col,row,SZ=200,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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 16220 KB Output is correct
2 Correct 56 ms 16220 KB Output is correct
3 Correct 95 ms 19096 KB Output is correct
4 Correct 57 ms 16220 KB Output is correct
5 Correct 56 ms 16220 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8428 KB Output is correct
8 Correct 4 ms 8536 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 8692 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 4 ms 8484 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 4 ms 8668 KB Output is correct
11 Correct 41 ms 10832 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 9012 KB Output is correct
2 Correct 274 ms 9052 KB Output is correct
3 Correct 269 ms 8796 KB Output is correct
4 Correct 285 ms 9052 KB Output is correct
5 Correct 269 ms 9052 KB Output is correct
6 Correct 4 ms 8536 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 1174 ms 9000 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 20316 KB Output is correct
2 Correct 67 ms 20312 KB Output is correct
3 Correct 61 ms 20316 KB Output is correct
4 Incorrect 78 ms 21588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 266 ms 9048 KB Output is correct
2 Correct 271 ms 9048 KB Output is correct
3 Correct 262 ms 8792 KB Output is correct
4 Correct 274 ms 9048 KB Output is correct
5 Correct 261 ms 9052 KB Output is correct
6 Correct 59 ms 20316 KB Output is correct
7 Correct 75 ms 20316 KB Output is correct
8 Correct 59 ms 20312 KB Output is correct
9 Incorrect 78 ms 21588 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 9052 KB Output is correct
2 Correct 314 ms 9128 KB Output is correct
3 Correct 272 ms 8796 KB Output is correct
4 Correct 288 ms 9148 KB Output is correct
5 Correct 288 ms 8948 KB Output is correct
6 Correct 67 ms 20392 KB Output is correct
7 Correct 65 ms 20312 KB Output is correct
8 Correct 63 ms 20316 KB Output is correct
9 Incorrect 92 ms 21540 KB Output isn't correct
10 Halted 0 ms 0 KB -