oj.uz

Submission #1023864

# Submission time Handle Problem Language Result Execution time Memory
1023864 2024-07-15T08:03:53 Z boyliguanhan Wombats (IOI13_wombats) C++17
100 / 100
 17355 ms 20740 KB 
#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

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 43 ms 14936 KB Output is correct
2 Correct 43 ms 14940 KB Output is correct
3 Correct 76 ms 16704 KB Output is correct
4 Correct 43 ms 14936 KB Output is correct
5 Correct 43 ms 14936 KB Output is correct
6 Correct 4 ms 8536 KB Output is correct
7 Correct 4 ms 8540 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 3 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 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8536 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 4 ms 8544 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 41 ms 9568 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 274 ms 9060 KB Output is correct
2 Correct 272 ms 9052 KB Output is correct
3 Correct 264 ms 8792 KB Output is correct
4 Correct 271 ms 9064 KB Output is correct
5 Correct 269 ms 9048 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 4 ms 8792 KB Output is correct
9 Correct 1264 ms 9060 KB Output is correct
10 Correct 4 ms 8536 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 19036 KB Output is correct
2 Correct 50 ms 19032 KB Output is correct
3 Correct 47 ms 19036 KB Output is correct
4 Correct 66 ms 19620 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 9048 KB Output is correct
2 Correct 277 ms 9048 KB Output is correct
3 Correct 259 ms 8908 KB Output is correct
4 Correct 267 ms 9052 KB Output is correct
5 Correct 263 ms 9048 KB Output is correct
6 Correct 46 ms 19060 KB Output is correct
7 Correct 46 ms 19036 KB Output is correct
8 Correct 46 ms 19032 KB Output is correct
9 Correct 64 ms 19796 KB Output is correct
10 Correct 43 ms 14936 KB Output is correct
11 Correct 42 ms 14936 KB Output is correct
12 Correct 76 ms 16684 KB Output is correct
13 Correct 42 ms 14936 KB Output is correct
14 Correct 45 ms 14940 KB Output is correct
15 Correct 4 ms 8536 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 3 ms 8540 KB Output is correct
18 Correct 4 ms 8540 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8612 KB Output is correct
21 Correct 4 ms 8528 KB Output is correct
22 Correct 4 ms 8540 KB Output is correct
23 Correct 3 ms 8540 KB Output is correct
24 Correct 4 ms 8540 KB Output is correct
25 Correct 40 ms 9644 KB Output is correct
26 Correct 4 ms 8536 KB Output is correct
27 Correct 1282 ms 9060 KB Output is correct
28 Correct 4534 ms 19540 KB Output is correct
29 Correct 4653 ms 17644 KB Output is correct
30 Correct 4273 ms 17604 KB Output is correct
31 Correct 4666 ms 20388 KB Output is correct
32 Correct 5 ms 8540 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 9052 KB Output is correct
2 Correct 266 ms 9052 KB Output is correct
3 Correct 265 ms 8796 KB Output is correct
4 Correct 277 ms 9072 KB Output is correct
5 Correct 273 ms 9300 KB Output is correct
6 Correct 45 ms 19036 KB Output is correct
7 Correct 47 ms 19032 KB Output is correct
8 Correct 50 ms 19036 KB Output is correct
9 Correct 64 ms 19796 KB Output is correct
10 Correct 43 ms 14940 KB Output is correct
11 Correct 43 ms 14940 KB Output is correct
12 Correct 77 ms 16700 KB Output is correct
13 Correct 42 ms 14936 KB Output is correct
14 Correct 42 ms 14936 KB Output is correct
15 Correct 722 ms 19284 KB Output is correct
16 Correct 17355 ms 20740 KB Output is correct
17 Correct 4 ms 8536 KB Output is correct
18 Correct 3 ms 8540 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 8540 KB Output is correct
23 Correct 4 ms 8540 KB Output is correct
24 Correct 3 ms 8540 KB Output is correct
25 Correct 4 ms 8476 KB Output is correct
26 Correct 4 ms 8620 KB Output is correct
27 Correct 46 ms 9556 KB Output is correct
28 Correct 4 ms 8536 KB Output is correct
29 Correct 1173 ms 9060 KB Output is correct
30 Correct 4296 ms 19536 KB Output is correct
31 Correct 16532 ms 19976 KB Output is correct
32 Correct 17092 ms 19864 KB Output is correct
33 Correct 4547 ms 17588 KB Output is correct
34 Correct 16082 ms 18056 KB Output is correct
35 Correct 4101 ms 17492 KB Output is correct
36 Correct 15510 ms 18052 KB Output is correct
37 Correct 4453 ms 20560 KB Output is correct
38 Correct 16283 ms 20560 KB Output is correct
39 Correct 4 ms 8536 KB Output is correct
40 Correct 16270 ms 18012 KB Output is correct