oj.uz

Submission #1031367

# Submission time Handle Problem Language Result Execution time Memory
1031367 2024-07-22T18:37:48 Z tolbi Wombats (IOI13_wombats) C++17
76 / 100
 1143 ms 262144 KB 
#pragma GCC optimize("O3,unroll-loops,fast-math")
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 5000;
const int MAXC = 200;
const int INF = 1e9;
constexpr int BLOK = 9;
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 17240 KB Output is correct
2 Correct 10 ms 17244 KB Output is correct
3 Correct 44 ms 18808 KB Output is correct
4 Correct 10 ms 17244 KB Output is correct
5 Correct 9 ms 17244 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 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 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 656 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 37 ms 1760 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 78 ms 3420 KB Output is correct
2 Correct 59 ms 3420 KB Output is correct
3 Correct 77 ms 3416 KB Output is correct
4 Correct 75 ms 3420 KB Output is correct
5 Correct 74 ms 3420 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 264 ms 3616 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27068 KB Output is correct
2 Correct 13 ms 26968 KB Output is correct
3 Correct 17 ms 27124 KB Output is correct
4 Correct 33 ms 27732 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3416 KB Output is correct
2 Correct 58 ms 3420 KB Output is correct
3 Correct 79 ms 3620 KB Output is correct
4 Correct 82 ms 3624 KB Output is correct
5 Correct 78 ms 3416 KB Output is correct
6 Correct 14 ms 27020 KB Output is correct
7 Correct 14 ms 26968 KB Output is correct
8 Correct 16 ms 26972 KB Output is correct
9 Correct 32 ms 27740 KB Output is correct
10 Correct 9 ms 17244 KB Output is correct
11 Correct 10 ms 17216 KB Output is correct
12 Correct 45 ms 18772 KB Output is correct
13 Correct 10 ms 17240 KB Output is correct
14 Correct 11 ms 17244 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 860 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 0 ms 860 KB Output is correct
21 Correct 0 ms 860 KB Output is correct
22 Correct 1 ms 668 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 42 ms 1676 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 256 ms 3416 KB Output is correct
28 Correct 752 ms 184696 KB Output is correct
29 Correct 729 ms 97876 KB Output is correct
30 Correct 774 ms 97876 KB Output is correct
31 Correct 753 ms 185672 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 75 ms 3416 KB Output is correct
2 Correct 58 ms 3420 KB Output is correct
3 Correct 78 ms 3420 KB Output is correct
4 Correct 83 ms 3528 KB Output is correct
5 Correct 73 ms 3596 KB Output is correct
6 Correct 13 ms 26972 KB Output is correct
7 Correct 13 ms 26972 KB Output is correct
8 Correct 15 ms 26972 KB Output is correct
9 Correct 35 ms 27728 KB Output is correct
10 Correct 10 ms 17244 KB Output is correct
11 Correct 10 ms 17244 KB Output is correct
12 Correct 45 ms 18784 KB Output is correct
13 Correct 10 ms 17240 KB Output is correct
14 Correct 10 ms 17244 KB Output is correct
15 Runtime error 1143 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -