oj.uz

Submission #1028876

# Submission time Handle Problem Language Result Execution time Memory
1028876 2024-07-20T09:47:28 Z tolbi Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 35344 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 5000;
const int MAXC = 200;
typedef long long ll;
const ll INF = 1e15;
ll H[MAXR][MAXC]={},V[MAXR][MAXC]={};
int C,R;
void init(int RR, int CC, int HH[5000][200], int VV[5000][200]) {
    C=CC,R=RR;
    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];
        }
    }
}

void changeH(int P, int Q, int W) {
    H[P][Q]=W;
}

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
}
ll ans[MAXR][MAXC];
ll nans[MAXR][MAXC];
ll cur[MAXR][MAXC];
int opt[MAXR][MAXC];
int escape(int V1, int V2) {
    for (int i = 0; i < C; i++){
        for (int j = 0; j < C; j++){
            if (i==j) ans[i][j]=0;
            else ans[i][j]=INF;
        }
    }
    for (int x = 0; x < R; x++){
        for (int i = 0; i < C; i++){
            ll somma = 0;
            for (int j = i; j < C; j++){
                cur[i][j]=somma+V[x][j];
                somma+=H[x][j];
            }
            somma=0;
            for (int j = i-1; j >= 0; j--){
                somma+=H[x][j];
                cur[i][j]=somma+V[x][j];
            }
        }
        for (int i = C-1; i >= 0; i--){
            for (int j = 0; j < C; j++){
                int lbound = 0;
                if (j) lbound = opt[i][j-1];
                int rbound = C-1;
                if (i+1<C) rbound = opt[i+1][j];
                nans[i][j]=ans[i][lbound]+cur[lbound][j];
                opt[i][j]=lbound;
                for (int k = lbound; k <= rbound; k++){
                    if (ans[i][k]+cur[k][j]<nans[i][j]){
                        nans[i][j]=ans[i][k]+cur[k][j];
                        opt[i][j]=k;
                    }
                }
            }
        }
        for (int i = 0; i < C; i++){
            for (int j = 0; j < C; j++){
                ans[i][j]=nans[i][j];
            }
        }
    }
    return ans[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 21 ms 16984 KB Output is correct
2 Correct 23 ms 19136 KB Output is correct
3 Correct 7632 ms 19280 KB Output is correct
4 Correct 21 ms 19032 KB Output is correct
5 Correct 22 ms 16984 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 14 ms 14832 KB Output is correct
5 Correct 11 ms 14828 KB Output is correct
6 Correct 18 ms 14684 KB Output is correct
7 Correct 16 ms 14684 KB Output is correct
8 Correct 11 ms 14832 KB Output is correct
9 Correct 14 ms 14684 KB Output is correct
10 Correct 14 ms 14832 KB Output is correct
11 Correct 6696 ms 15272 KB Output is correct
12 Correct 13 ms 604 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 3528 KB Output is correct
2 Correct 356 ms 3420 KB Output is correct
3 Correct 496 ms 13056 KB Output is correct
4 Correct 535 ms 12896 KB Output is correct
5 Correct 543 ms 14940 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 398 ms 14940 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 24668 KB Output is correct
2 Correct 123 ms 24700 KB Output is correct
3 Correct 174 ms 24524 KB Output is correct
4 Correct 15369 ms 25940 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 14952 KB Output is correct
2 Correct 319 ms 14940 KB Output is correct
3 Correct 480 ms 14944 KB Output is correct
4 Correct 534 ms 14940 KB Output is correct
5 Correct 531 ms 14952 KB Output is correct
6 Correct 167 ms 24668 KB Output is correct
7 Correct 126 ms 24700 KB Output is correct
8 Correct 177 ms 24720 KB Output is correct
9 Correct 14425 ms 25944 KB Output is correct
10 Correct 20 ms 16988 KB Output is correct
11 Correct 20 ms 16988 KB Output is correct
12 Correct 7529 ms 19796 KB Output is correct
13 Correct 20 ms 19144 KB Output is correct
14 Correct 21 ms 19136 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Correct 1 ms 10588 KB Output is correct
17 Correct 1 ms 10588 KB Output is correct
18 Correct 15 ms 14684 KB Output is correct
19 Correct 11 ms 14684 KB Output is correct
20 Correct 13 ms 14836 KB Output is correct
21 Correct 11 ms 14684 KB Output is correct
22 Correct 11 ms 14684 KB Output is correct
23 Correct 14 ms 14684 KB Output is correct
24 Correct 12 ms 14684 KB Output is correct
25 Correct 6255 ms 17140 KB Output is correct
26 Correct 12 ms 14684 KB Output is correct
27 Correct 346 ms 14940 KB Output is correct
28 Execution timed out 20103 ms 28500 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 14960 KB Output is correct
2 Correct 351 ms 14940 KB Output is correct
3 Correct 521 ms 14940 KB Output is correct
4 Correct 470 ms 15188 KB Output is correct
5 Correct 457 ms 14940 KB Output is correct
6 Correct 162 ms 24916 KB Output is correct
7 Correct 114 ms 24668 KB Output is correct
8 Correct 152 ms 24520 KB Output is correct
9 Correct 14501 ms 25944 KB Output is correct
10 Correct 22 ms 16988 KB Output is correct
11 Correct 31 ms 16988 KB Output is correct
12 Correct 7681 ms 19800 KB Output is correct
13 Correct 23 ms 16988 KB Output is correct
14 Correct 22 ms 16988 KB Output is correct
15 Correct 4711 ms 35344 KB Output is correct
16 Execution timed out 20036 ms 33388 KB Time limit exceeded
17 Halted 0 ms 0 KB -