oj.uz

Submission #1023858

# Submission time Handle Problem Language Result Execution time Memory
1023858 2024-07-15T07:57:30 Z vjudge1 Wombats (IOI13_wombats) C++17
55 / 100
 12651 ms 29276 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-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=210,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

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16216 KB Output is correct
2 Correct 56 ms 16032 KB Output is correct
3 Correct 90 ms 17748 KB Output is correct
4 Correct 56 ms 16256 KB Output is correct
5 Correct 56 ms 16216 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8448 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 4 ms 8540 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 8540 KB Output is correct
9 Correct 4 ms 8536 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 40 ms 9480 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 9052 KB Output is correct
2 Correct 270 ms 9048 KB Output is correct
3 Correct 264 ms 9048 KB Output is correct
4 Correct 273 ms 9048 KB Output is correct
5 Correct 270 ms 9056 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 1200 ms 9076 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 20056 KB Output is correct
2 Correct 58 ms 20060 KB Output is correct
3 Correct 58 ms 20008 KB Output is correct
4 Correct 77 ms 20820 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 9048 KB Output is correct
2 Correct 274 ms 9052 KB Output is correct
3 Correct 261 ms 8908 KB Output is correct
4 Correct 274 ms 9052 KB Output is correct
5 Correct 275 ms 9056 KB Output is correct
6 Correct 63 ms 20056 KB Output is correct
7 Correct 62 ms 20060 KB Output is correct
8 Correct 59 ms 20056 KB Output is correct
9 Correct 76 ms 20820 KB Output is correct
10 Correct 55 ms 16220 KB Output is correct
11 Correct 55 ms 16220 KB Output is correct
12 Correct 92 ms 18940 KB Output is correct
13 Correct 55 ms 16220 KB Output is correct
14 Correct 54 ms 16220 KB Output is correct
15 Correct 4 ms 8536 KB Output is correct
16 Correct 4 ms 8540 KB Output is correct
17 Correct 5 ms 8540 KB Output is correct
18 Correct 4 ms 8560 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8540 KB Output is correct
21 Correct 4 ms 8540 KB Output is correct
22 Correct 4 ms 8624 KB Output is correct
23 Correct 5 ms 8540 KB Output is correct
24 Correct 4 ms 8436 KB Output is correct
25 Correct 41 ms 10816 KB Output is correct
26 Correct 4 ms 8792 KB Output is correct
27 Correct 1171 ms 9052 KB Output is correct
28 Incorrect 3362 ms 23856 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 9048 KB Output is correct
2 Correct 294 ms 9064 KB Output is correct
3 Correct 269 ms 8796 KB Output is correct
4 Correct 289 ms 8912 KB Output is correct
5 Correct 284 ms 9056 KB Output is correct
6 Correct 60 ms 20056 KB Output is correct
7 Correct 62 ms 20060 KB Output is correct
8 Correct 61 ms 20008 KB Output is correct
9 Correct 79 ms 20820 KB Output is correct
10 Correct 60 ms 16216 KB Output is correct
11 Correct 60 ms 16216 KB Output is correct
12 Correct 99 ms 18928 KB Output is correct
13 Correct 73 ms 16216 KB Output is correct
14 Correct 57 ms 16216 KB Output is correct
15 Correct 702 ms 28496 KB Output is correct
16 Correct 12651 ms 29276 KB Output is correct
17 Correct 5 ms 8536 KB Output is correct
18 Correct 4 ms 8536 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8540 KB Output is correct
21 Correct 4 ms 8436 KB Output is correct
22 Correct 4 ms 8564 KB Output is correct
23 Correct 4 ms 8540 KB Output is correct
24 Correct 4 ms 8540 KB Output is correct
25 Correct 4 ms 8624 KB Output is correct
26 Correct 4 ms 8540 KB Output is correct
27 Correct 40 ms 11028 KB Output is correct
28 Correct 4 ms 8536 KB Output is correct
29 Correct 1267 ms 9132 KB Output is correct
30 Incorrect 3361 ms 23652 KB Output isn't correct
31 Halted 0 ms 0 KB -