oj.uz

Submission #1031350

# Submission time Handle Problem Language Result Execution time Memory
1031350 2024-07-22T18:23:21 Z tolbi Wombats (IOI13_wombats) C++17
76 / 100
 6978 ms 35956 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 5003;
const int MAXC = 103;
const int INF = 1e9;
const int BL = 200;
int H[MAXR][MAXC]={},V[MAXR][MAXC]={};
int dp[BL*4][MAXC][MAXC];
int opt[MAXC][MAXC];
int cur[MAXC][MAXC];
int C,R,sz;
constexpr int BLOK = 300;
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 6492 KB Output is correct
2 Correct 4 ms 6680 KB Output is correct
3 Correct 39 ms 9372 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 4 ms 6492 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 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 2904 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 1360 KB Output is correct
2 Correct 357 ms 860 KB Output is correct
3 Correct 481 ms 860 KB Output is correct
4 Correct 536 ms 936 KB Output is correct
5 Correct 464 ms 932 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1854 ms 944 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12488 KB Output is correct
2 Correct 9 ms 12636 KB Output is correct
3 Correct 9 ms 12708 KB Output is correct
4 Correct 28 ms 13912 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 860 KB Output is correct
2 Correct 357 ms 924 KB Output is correct
3 Correct 485 ms 860 KB Output is correct
4 Correct 501 ms 860 KB Output is correct
5 Correct 478 ms 860 KB Output is correct
6 Correct 10 ms 12636 KB Output is correct
7 Correct 9 ms 12692 KB Output is correct
8 Correct 10 ms 12632 KB Output is correct
9 Correct 29 ms 13916 KB Output is correct
10 Correct 4 ms 6600 KB Output is correct
11 Correct 4 ms 6492 KB Output is correct
12 Correct 39 ms 9356 KB Output is correct
13 Correct 5 ms 6492 KB Output is correct
14 Correct 5 ms 6712 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 41 ms 2772 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1880 ms 952 KB Output is correct
28 Correct 5738 ms 19028 KB Output is correct
29 Correct 6978 ms 15324 KB Output is correct
30 Correct 6582 ms 15312 KB Output is correct
31 Correct 5982 ms 20820 KB Output is correct
32 Correct 0 ms 344 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 856 KB Output is correct
2 Correct 347 ms 856 KB Output is correct
3 Correct 465 ms 860 KB Output is correct
4 Correct 467 ms 856 KB Output is correct
5 Correct 459 ms 860 KB Output is correct
6 Correct 11 ms 12652 KB Output is correct
7 Correct 8 ms 12636 KB Output is correct
8 Correct 9 ms 12708 KB Output is correct
9 Correct 29 ms 13908 KB Output is correct
10 Correct 4 ms 6488 KB Output is correct
11 Correct 4 ms 6488 KB Output is correct
12 Correct 38 ms 9416 KB Output is correct
13 Correct 5 ms 6492 KB Output is correct
14 Correct 5 ms 6492 KB Output is correct
15 Runtime error 122 ms 35956 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -