oj.uz

Submission #1028894

# Submission time Handle Problem Language Result Execution time Memory
1028894 2024-07-20T10:05:34 Z tolbi Wombats (IOI13_wombats) C++17
55 / 100
 247 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 5000;
const int MAXC = 100;
typedef long long ll;
const ll INF = 1e15;
ll H[MAXR][MAXC]={},V[MAXR][MAXC]={};
ll 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 26 ms 76116 KB Output is correct
2 Correct 27 ms 76124 KB Output is correct
3 Correct 88 ms 78932 KB Output is correct
4 Correct 27 ms 76196 KB Output is correct
5 Correct 25 ms 76232 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 39 ms 3924 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 20864 KB Output is correct
2 Correct 46 ms 20824 KB Output is correct
3 Correct 71 ms 20824 KB Output is correct
4 Correct 67 ms 22608 KB Output is correct
5 Correct 75 ms 22616 KB Output is correct
6 Correct 1 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 190 ms 20848 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 96384 KB Output is correct
2 Correct 33 ms 96336 KB Output is correct
3 Correct 34 ms 96348 KB Output is correct
4 Correct 53 ms 97636 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 20824 KB Output is correct
2 Correct 46 ms 22620 KB Output is correct
3 Correct 58 ms 22620 KB Output is correct
4 Correct 63 ms 22616 KB Output is correct
5 Correct 60 ms 22616 KB Output is correct
6 Correct 39 ms 96340 KB Output is correct
7 Correct 32 ms 96344 KB Output is correct
8 Correct 32 ms 96460 KB Output is correct
9 Correct 55 ms 97708 KB Output is correct
10 Correct 25 ms 76112 KB Output is correct
11 Correct 24 ms 76124 KB Output is correct
12 Correct 73 ms 79072 KB Output is correct
13 Correct 25 ms 76088 KB Output is correct
14 Correct 27 ms 76120 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 1628 KB Output is correct
19 Correct 1 ms 1628 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct
21 Correct 1 ms 1628 KB Output is correct
22 Correct 1 ms 1628 KB Output is correct
23 Correct 1 ms 1732 KB Output is correct
24 Correct 1 ms 1628 KB Output is correct
25 Correct 38 ms 3920 KB Output is correct
26 Correct 1 ms 1628 KB Output is correct
27 Correct 175 ms 20840 KB Output is correct
28 Runtime error 141 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 59 ms 22616 KB Output is correct
2 Correct 52 ms 22864 KB Output is correct
3 Correct 58 ms 22620 KB Output is correct
4 Correct 57 ms 22620 KB Output is correct
5 Correct 55 ms 22620 KB Output is correct
6 Correct 33 ms 96376 KB Output is correct
7 Correct 33 ms 96388 KB Output is correct
8 Correct 34 ms 96344 KB Output is correct
9 Correct 51 ms 97196 KB Output is correct
10 Correct 27 ms 76124 KB Output is correct
11 Correct 25 ms 76116 KB Output is correct
12 Correct 63 ms 77904 KB Output is correct
13 Correct 25 ms 76112 KB Output is correct
14 Correct 25 ms 76192 KB Output is correct
15 Runtime error 247 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -