oj.uz

Submission #1031354

# Submission time Handle Problem Language Result Execution time Memory
1031354 2024-07-22T18:28:22 Z tolbi Wombats (IOI13_wombats) C++17
100 / 100
 10210 ms 45904 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 = 100;
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 5 ms 9052 KB Output is correct
2 Correct 6 ms 9052 KB Output is correct
3 Correct 42 ms 10580 KB Output is correct
4 Correct 6 ms 9048 KB Output is correct
5 Correct 6 ms 9052 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 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 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 37 ms 1664 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 514 ms 1164 KB Output is correct
2 Correct 312 ms 1112 KB Output is correct
3 Correct 510 ms 1116 KB Output is correct
4 Correct 512 ms 1116 KB Output is correct
5 Correct 470 ms 1112 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 1796 ms 1176 KB Output is correct
10 Correct 0 ms 600 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16988 KB Output is correct
2 Correct 11 ms 16892 KB Output is correct
3 Correct 13 ms 16796 KB Output is correct
4 Correct 29 ms 17756 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 1368 KB Output is correct
2 Correct 329 ms 1116 KB Output is correct
3 Correct 481 ms 1116 KB Output is correct
4 Correct 489 ms 1116 KB Output is correct
5 Correct 484 ms 1168 KB Output is correct
6 Correct 10 ms 16984 KB Output is correct
7 Correct 10 ms 16988 KB Output is correct
8 Correct 10 ms 17036 KB Output is correct
9 Correct 28 ms 17756 KB Output is correct
10 Correct 5 ms 9052 KB Output is correct
11 Correct 8 ms 9052 KB Output is correct
12 Correct 40 ms 10616 KB Output is correct
13 Correct 6 ms 9048 KB Output is correct
14 Correct 9 ms 9048 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 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 604 KB Output is correct
23 Correct 0 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 37 ms 1484 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1788 ms 1172 KB Output is correct
28 Correct 2362 ms 27264 KB Output is correct
29 Correct 2857 ms 24656 KB Output is correct
30 Correct 2857 ms 24404 KB Output is correct
31 Correct 2221 ms 28440 KB Output is correct
32 Correct 1 ms 600 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 1168 KB Output is correct
2 Correct 313 ms 1116 KB Output is correct
3 Correct 449 ms 1172 KB Output is correct
4 Correct 437 ms 1112 KB Output is correct
5 Correct 442 ms 1192 KB Output is correct
6 Correct 9 ms 16988 KB Output is correct
7 Correct 9 ms 16988 KB Output is correct
8 Correct 9 ms 16952 KB Output is correct
9 Correct 27 ms 17756 KB Output is correct
10 Correct 7 ms 9052 KB Output is correct
11 Correct 5 ms 9052 KB Output is correct
12 Correct 34 ms 10540 KB Output is correct
13 Correct 5 ms 8796 KB Output is correct
14 Correct 5 ms 9048 KB Output is correct
15 Correct 792 ms 37056 KB Output is correct
16 Correct 9741 ms 39764 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 0 ms 700 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 1 ms 700 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 38 ms 2896 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1758 ms 1244 KB Output is correct
30 Correct 2059 ms 31176 KB Output is correct
31 Correct 7747 ms 45504 KB Output is correct
32 Correct 7525 ms 45528 KB Output is correct
33 Correct 2751 ms 27936 KB Output is correct
34 Correct 10210 ms 42048 KB Output is correct
35 Correct 2767 ms 27988 KB Output is correct
36 Correct 10046 ms 42008 KB Output is correct
37 Correct 2117 ms 32848 KB Output is correct
38 Correct 7887 ms 45904 KB Output is correct
39 Correct 0 ms 856 KB Output is correct
40 Correct 9863 ms 42264 KB Output is correct