oj.uz

Submission #1023861

# Submission time Handle Problem Language Result Execution time Memory
1023861 2024-07-15T08:00:25 Z vjudge1 Wombats (IOI13_wombats) C++17
100 / 100
 17031 ms 20940 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 42 ms 14940 KB Output is correct
2 Correct 42 ms 14940 KB Output is correct
3 Correct 75 ms 16720 KB Output is correct
4 Correct 54 ms 14940 KB Output is correct
5 Correct 41 ms 14936 KB Output is correct
6 Correct 3 ms 8536 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 3 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 5 ms 8540 KB Output is correct
3 Correct 5 ms 8388 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 8576 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 5 ms 8592 KB Output is correct
9 Correct 5 ms 8540 KB Output is correct
10 Correct 5 ms 8512 KB Output is correct
11 Correct 76 ms 9588 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 268 ms 9048 KB Output is correct
2 Correct 263 ms 9052 KB Output is correct
3 Correct 267 ms 8792 KB Output is correct
4 Correct 274 ms 9052 KB Output is correct
5 Correct 273 ms 9048 KB Output is correct
6 Correct 5 ms 8536 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 1257 ms 9064 KB Output is correct
10 Correct 6 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 19032 KB Output is correct
2 Correct 46 ms 19060 KB Output is correct
3 Correct 59 ms 19036 KB Output is correct
4 Correct 66 ms 19792 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 9300 KB Output is correct
2 Correct 273 ms 9048 KB Output is correct
3 Correct 266 ms 8908 KB Output is correct
4 Correct 272 ms 9048 KB Output is correct
5 Correct 266 ms 9048 KB Output is correct
6 Correct 47 ms 19032 KB Output is correct
7 Correct 47 ms 19036 KB Output is correct
8 Correct 46 ms 19032 KB Output is correct
9 Correct 66 ms 19788 KB Output is correct
10 Correct 46 ms 14936 KB Output is correct
11 Correct 42 ms 14936 KB Output is correct
12 Correct 79 ms 16720 KB Output is correct
13 Correct 43 ms 14940 KB Output is correct
14 Correct 43 ms 14936 KB Output is correct
15 Correct 5 ms 8540 KB Output is correct
16 Correct 4 ms 8540 KB Output is correct
17 Correct 4 ms 8792 KB Output is correct
18 Correct 5 ms 8540 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8512 KB Output is correct
21 Correct 4 ms 8616 KB Output is correct
22 Correct 6 ms 8540 KB Output is correct
23 Correct 6 ms 8600 KB Output is correct
24 Correct 4 ms 8536 KB Output is correct
25 Correct 40 ms 9556 KB Output is correct
26 Correct 4 ms 8540 KB Output is correct
27 Correct 1189 ms 9060 KB Output is correct
28 Correct 4414 ms 19484 KB Output is correct
29 Correct 4529 ms 17632 KB Output is correct
30 Correct 4407 ms 17664 KB Output is correct
31 Correct 4799 ms 20444 KB Output is correct
32 Correct 5 ms 8536 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 9052 KB Output is correct
2 Correct 280 ms 9056 KB Output is correct
3 Correct 287 ms 8796 KB Output is correct
4 Correct 274 ms 9048 KB Output is correct
5 Correct 257 ms 9056 KB Output is correct
6 Correct 45 ms 19056 KB Output is correct
7 Correct 47 ms 19036 KB Output is correct
8 Correct 48 ms 19032 KB Output is correct
9 Correct 69 ms 19800 KB Output is correct
10 Correct 42 ms 14940 KB Output is correct
11 Correct 49 ms 14936 KB Output is correct
12 Correct 77 ms 16724 KB Output is correct
13 Correct 42 ms 14936 KB Output is correct
14 Correct 51 ms 15052 KB Output is correct
15 Correct 754 ms 19340 KB Output is correct
16 Correct 17031 ms 20940 KB Output is correct
17 Correct 5 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 5 ms 8536 KB Output is correct
21 Correct 4 ms 8540 KB Output is correct
22 Correct 5 ms 8540 KB Output is correct
23 Correct 5 ms 8540 KB Output is correct
24 Correct 4 ms 8536 KB Output is correct
25 Correct 4 ms 8540 KB Output is correct
26 Correct 4 ms 8540 KB Output is correct
27 Correct 40 ms 9556 KB Output is correct
28 Correct 4 ms 8536 KB Output is correct
29 Correct 1288 ms 9056 KB Output is correct
30 Correct 4557 ms 19472 KB Output is correct
31 Correct 16975 ms 19832 KB Output is correct
32 Correct 16201 ms 20004 KB Output is correct
33 Correct 4558 ms 17520 KB Output is correct
34 Correct 15301 ms 18148 KB Output is correct
35 Correct 4082 ms 17620 KB Output is correct
36 Correct 15688 ms 18012 KB Output is correct
37 Correct 4279 ms 20564 KB Output is correct
38 Correct 15803 ms 20520 KB Output is correct
39 Correct 4 ms 8536 KB Output is correct
40 Correct 16410 ms 17948 KB Output is correct