oj.uz

Submission #1031361

# Submission time Handle Problem Language Result Execution time Memory
1031361 2024-07-22T18:34:56 Z tolbi Wombats (IOI13_wombats) C++17
76 / 100
 1102 ms 262144 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 = 7;
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 10 ms 17244 KB Output is correct
2 Correct 10 ms 17244 KB Output is correct
3 Correct 45 ms 18792 KB Output is correct
4 Correct 10 ms 17244 KB Output is correct
5 Correct 11 ms 17200 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

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 0 ms 604 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 860 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 37 ms 1624 KB Output is correct
12 Correct 1 ms 860 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3676 KB Output is correct
2 Correct 55 ms 3420 KB Output is correct
3 Correct 71 ms 3676 KB Output is correct
4 Correct 68 ms 3672 KB Output is correct
5 Correct 67 ms 3416 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 252 ms 3616 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 20 ms 26712 KB Output is correct
2 Correct 15 ms 26716 KB Output is correct
3 Correct 13 ms 26716 KB Output is correct
4 Correct 63 ms 27620 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3676 KB Output is correct
2 Correct 64 ms 3420 KB Output is correct
3 Correct 85 ms 3664 KB Output is correct
4 Correct 77 ms 3468 KB Output is correct
5 Correct 76 ms 3420 KB Output is correct
6 Correct 17 ms 26608 KB Output is correct
7 Correct 13 ms 26716 KB Output is correct
8 Correct 14 ms 26712 KB Output is correct
9 Correct 34 ms 27516 KB Output is correct
10 Correct 10 ms 17244 KB Output is correct
11 Correct 10 ms 17244 KB Output is correct
12 Correct 46 ms 18776 KB Output is correct
13 Correct 10 ms 17244 KB Output is correct
14 Correct 9 ms 17260 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 1 ms 860 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 0 ms 860 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 1 ms 856 KB Output is correct
24 Correct 0 ms 860 KB Output is correct
25 Correct 79 ms 1620 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 248 ms 3664 KB Output is correct
28 Correct 773 ms 187044 KB Output is correct
29 Correct 821 ms 184268 KB Output is correct
30 Correct 817 ms 184144 KB Output is correct
31 Correct 787 ms 188092 KB Output is correct
32 Correct 0 ms 604 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3560 KB Output is correct
2 Correct 55 ms 3420 KB Output is correct
3 Correct 69 ms 3684 KB Output is correct
4 Correct 68 ms 3672 KB Output is correct
5 Correct 67 ms 3564 KB Output is correct
6 Correct 14 ms 26716 KB Output is correct
7 Correct 13 ms 26756 KB Output is correct
8 Correct 13 ms 26716 KB Output is correct
9 Correct 32 ms 27592 KB Output is correct
10 Correct 10 ms 17240 KB Output is correct
11 Correct 10 ms 17244 KB Output is correct
12 Correct 45 ms 18776 KB Output is correct
13 Correct 10 ms 17244 KB Output is correct
14 Correct 10 ms 17244 KB Output is correct
15 Runtime error 1102 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -