oj.uz

Submission #1028903

# Submission time Handle Problem Language Result Execution time Memory
1028903 2024-07-20T10:08:28 Z tolbi Wombats (IOI13_wombats) C++17
55 / 100
 330 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 5003;
const int MAXC = 103;
const int INF = 1e9;
int H[MAXR][MAXC]={},V[MAXR][MAXC]={};
int dp[MAXR*4][MAXC][MAXC];
int opt[MAXC][MAXC];
int C,R,sz;
void merge(int x){
    if (x*2+1>=sz){
        if (x-sz/2<R){
            for (int i = 0; i < C; i++){
                int somma = 0;
                for (int j = i; j < C; j++){
                    dp[x][i][j]=somma+V[x-sz/2][j];
                    somma+=H[x-sz/2][j];
                }
                somma = 0;
                for (int j = i-1; j >= 0; j--){
                    somma+=H[x-sz/2][j];
                    dp[x][i][j]=somma+V[x-sz/2][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)+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+=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+=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 29 ms 73052 KB Output is correct
2 Correct 25 ms 73596 KB Output is correct
3 Correct 67 ms 75596 KB Output is correct
4 Correct 26 ms 73048 KB Output is correct
5 Correct 25 ms 73048 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 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 2492 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 1168 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 1220 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 45 ms 3412 KB Output is correct
12 Correct 1 ms 1112 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11356 KB Output is correct
2 Correct 39 ms 11356 KB Output is correct
3 Correct 52 ms 13144 KB Output is correct
4 Correct 48 ms 13148 KB Output is correct
5 Correct 48 ms 13148 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 151 ms 13368 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 85844 KB Output is correct
2 Correct 39 ms 85844 KB Output is correct
3 Correct 35 ms 85688 KB Output is correct
4 Correct 52 ms 87204 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13148 KB Output is correct
2 Correct 40 ms 13144 KB Output is correct
3 Correct 50 ms 13144 KB Output is correct
4 Correct 50 ms 11396 KB Output is correct
5 Correct 56 ms 11396 KB Output is correct
6 Correct 30 ms 85844 KB Output is correct
7 Correct 46 ms 85840 KB Output is correct
8 Correct 47 ms 85840 KB Output is correct
9 Correct 60 ms 87124 KB Output is correct
10 Correct 26 ms 75088 KB Output is correct
11 Correct 28 ms 73044 KB Output is correct
12 Correct 64 ms 75708 KB Output is correct
13 Correct 28 ms 73164 KB Output is correct
14 Correct 28 ms 73196 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 2 ms 3164 KB Output is correct
21 Correct 1 ms 3164 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 42 ms 3220 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 171 ms 11396 KB Output is correct
28 Runtime error 176 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 11204 KB Output is correct
2 Correct 39 ms 13148 KB Output is correct
3 Correct 52 ms 13148 KB Output is correct
4 Correct 49 ms 13144 KB Output is correct
5 Correct 53 ms 13360 KB Output is correct
6 Correct 32 ms 85844 KB Output is correct
7 Correct 33 ms 85844 KB Output is correct
8 Correct 31 ms 85852 KB Output is correct
9 Correct 51 ms 87052 KB Output is correct
10 Correct 26 ms 73052 KB Output is correct
11 Correct 25 ms 73012 KB Output is correct
12 Correct 63 ms 75572 KB Output is correct
13 Correct 27 ms 73052 KB Output is correct
14 Correct 25 ms 73196 KB Output is correct
15 Runtime error 330 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -