oj.uz

Submission #1031356

# Submission time Handle Problem Language Result Execution time Memory
1031356 2024-07-22T18:30:45 Z tolbi Wombats (IOI13_wombats) C++17
100 / 100
 6298 ms 59260 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 5003;
const int MAXC = 203;
const int INF = 1e9;
constexpr int BLOK = 50;
int H[MAXR][MAXC]={},V[MAXR][MAXC]={};
int dp[(MAXR+BLOK-1)/BLOK*4][MAXC][MAXC];
int opt[MAXC][MAXC];
int cur[MAXC][MAXC];
int C,R,sz;
void merge(int x){
    if (x*2+1>=sz){
        if (x-sz/2<(R+BLOK-1)/BLOK){
            for (int i = 0; i < C; i++){
                for (int j = 0; j < C; j++){
                    dp[x][i][j]=INF;
                }
                dp[x][i][i]=0;
            }
            for (int _ = (x-sz/2)*BLOK; _ < min(R,(x-sz/2+1)*BLOK); _++){
                for (int i = 0; i < C; i++){
                    int somma = 0;
                    for (int j = i; j < C; j++){
                        cur[i][j]=somma+V[_][j];
                        somma+=H[_][j];
                    }
                    somma = 0;
                    for (int j = i-1; j >= 0; j--){
                        somma+=H[_][j];
                        cur[i][j]=somma+V[_][j];
                    }
                }
                int edp[MAXC][MAXC];
                for (int i = C-1; i >= 0; i--){
                    for (int j = 0; j < C; j++){
                        int lbound = 0;
                        int rbound = C-1;
                        if (j) lbound=opt[i][j-1];
                        if (i+1<C) rbound=opt[i+1][j];
                        edp[i][j]=dp[x][i][lbound]+cur[lbound][j];
                        opt[i][j]=lbound;
                        for (int k = lbound; k <= rbound; k++){
                            if (dp[x][i][k]+cur[k][j]<edp[i][j]){
                                edp[i][j]=dp[x][i][k]+cur[k][j];
                                opt[i][j]=k;
                            }
                        }
                    }
                }
                for (int i = 0; i < C; i++){
                    for (int j = 0; j < C; j++){
                        dp[x][i][j]=edp[i][j];
                    }
                }
            }
        }
        else {
            for (int i = 0; i < C; i++){
                for (int j = 0; j < C; j++){
                    if (i==j) dp[x][i][j]=0;
                    else dp[x][i][j]=INF;
                }
            }
        }
    }
    else {
        for (int i = C-1; i >= 0; i--){
            for (int j = 0; j < C; j++){
                int lbound = 0;
                int rbound = C-1;
                if (j) lbound=opt[i][j-1];
                if (i+1<C) rbound=opt[i+1][j];
                opt[i][j]=lbound;
                dp[x][i][j]=dp[x*2+1][i][lbound]+dp[x*2+2][lbound][j];
                for (int k = lbound; k <= rbound; k++){
                    if (dp[x*2+1][i][k]+dp[x*2+2][k][j]<dp[x][i][j]){
                        dp[x][i][j]=dp[x*2+1][i][k]+dp[x*2+2][k][j];
                        opt[i][j]=k;
                    }
                }
            }
        }
    }
}
void init(int RR, int CC, int HH[5000][200], int VV[5000][200]) {
    C=CC,R=RR;
    sz=(1LL<<((int)(ceil(log2((R+BLOK-1)/BLOK)+1))))-1;
    for (int i = 0; i < R; i++){
        for (int j = 0; j < C; j++){
            if (j+1<C) H[i][j]=HH[i][j];
            if (i+1<R) V[i][j]=VV[i][j];
        }
    }
    for (int i = sz-1; i >= 0; i--){
        merge(i);
    }
}

void changeH(int P, int Q, int W) {
    H[P][Q]=W;
    P/=BLOK;
    P+=sz/2;
    merge(P);
    while (P){
        P=(P-1)/2;
        merge(P);
    }
}

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
    P/=BLOK;
    P+=sz/2;
    merge(P);
    while (P){
        P=(P-1)/2;
        merge(P);
    }
}
int escape(int V1, int V2) {
    return dp[0][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 6 ms 9560 KB Output is correct
2 Correct 6 ms 9564 KB Output is correct
3 Correct 41 ms 11104 KB Output is correct
4 Correct 5 ms 9560 KB Output is correct
5 Correct 5 ms 9564 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 616 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 38 ms 1692 KB Output is correct
12 Correct 1 ms 600 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 1268 KB Output is correct
2 Correct 210 ms 1336 KB Output is correct
3 Correct 297 ms 1340 KB Output is correct
4 Correct 292 ms 1196 KB Output is correct
5 Correct 264 ms 1364 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 861 ms 1336 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17500 KB Output is correct
2 Correct 10 ms 17500 KB Output is correct
3 Correct 10 ms 17620 KB Output is correct
4 Correct 28 ms 18268 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 1112 KB Output is correct
2 Correct 155 ms 1116 KB Output is correct
3 Correct 228 ms 1264 KB Output is correct
4 Correct 239 ms 1336 KB Output is correct
5 Correct 226 ms 1116 KB Output is correct
6 Correct 9 ms 17496 KB Output is correct
7 Correct 9 ms 17496 KB Output is correct
8 Correct 9 ms 17500 KB Output is correct
9 Correct 24 ms 18268 KB Output is correct
10 Correct 5 ms 9564 KB Output is correct
11 Correct 5 ms 9460 KB Output is correct
12 Correct 35 ms 11092 KB Output is correct
13 Correct 7 ms 9564 KB Output is correct
14 Correct 6 ms 9616 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 0 ms 604 KB Output is correct
22 Correct 0 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 34 ms 1628 KB Output is correct
26 Correct 0 ms 600 KB Output is correct
27 Correct 793 ms 1332 KB Output is correct
28 Correct 1099 ms 37972 KB Output is correct
29 Correct 1541 ms 35124 KB Output is correct
30 Correct 1499 ms 35016 KB Output is correct
31 Correct 1251 ms 38992 KB Output is correct
32 Correct 0 ms 856 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 1340 KB Output is correct
2 Correct 193 ms 1112 KB Output is correct
3 Correct 264 ms 1336 KB Output is correct
4 Correct 322 ms 1116 KB Output is correct
5 Correct 262 ms 1112 KB Output is correct
6 Correct 12 ms 17496 KB Output is correct
7 Correct 10 ms 17500 KB Output is correct
8 Correct 12 ms 17684 KB Output is correct
9 Correct 28 ms 18264 KB Output is correct
10 Correct 6 ms 9560 KB Output is correct
11 Correct 6 ms 9564 KB Output is correct
12 Correct 41 ms 11124 KB Output is correct
13 Correct 6 ms 9564 KB Output is correct
14 Correct 6 ms 9564 KB Output is correct
15 Correct 1050 ms 57868 KB Output is correct
16 Correct 6200 ms 59260 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 0 ms 604 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 0 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 37 ms 1512 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 893 ms 1116 KB Output is correct
30 Correct 1282 ms 38060 KB Output is correct
31 Correct 4579 ms 58268 KB Output is correct
32 Correct 4594 ms 58364 KB Output is correct
33 Correct 1654 ms 35236 KB Output is correct
34 Correct 6050 ms 55632 KB Output is correct
35 Correct 1650 ms 35084 KB Output is correct
36 Correct 6238 ms 55528 KB Output is correct
37 Correct 1377 ms 38984 KB Output is correct
38 Correct 5045 ms 58964 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 6298 ms 55644 KB Output is correct