oj.uz

Submission #586679

# Submission time Handle Problem Language Result Execution time Memory
586679 2022-06-30T14:29:14 Z AlperenT Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

const int N = 5000 + 1, M = 100, INF = 1e9 + 5;

int n, m, h[N][M], v[N][M], dist[M][N][M];

void calc_dist(){
	for(int lst = 0; lst < m; lst++){
		for(int c = 0; c < m; c++) dist[lst][n][c] = INF;
		dist[lst][n][lst] = 0;

		for(int r = n - 1; r >= 0; r--){
			priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

			for(int c = 0; c < m; c++){
				dist[lst][r][c] = dist[lst][r + 1][c] + v[r][c];

				pq.push({dist[lst][r][c], c});
			}

			while(!pq.empty()){
				int d = pq.top().first, c = pq.top().second;
				pq.pop();

				if(c != 0){
					if(d + h[r][c - 1] < dist[lst][r][c - 1]){
						dist[lst][r][c - 1] = d + h[r][c - 1];
						pq.push({dist[lst][r][c - 1], c - 1});
					}
				}

				if(c != m - 1){
					if(d + h[r][c] < dist[lst][r][c + 1]){
						dist[lst][r][c + 1] = d + h[r][c];
						pq.push({dist[lst][r][c + 1], c + 1});
					}
				}
			}
		}
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;

    for(int i = 0; i < n; i++){
    	for(int j = 0; j < m - 1; j++){
    		h[i][j] = H[i][j];
    	}
    }

    for(int i = 0; i < n - 1; i++){
    	for(int j = 0; j < m; j++){
    		v[i][j] = V[i][j];
    	}
    }

    calc_dist();
}

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

    calc_dist();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;

    calc_dist();
}

int escape(int V1, int V2) {
    return dist[V2][0][V1];
}

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 75 ms 8020 KB Output is correct
2 Correct 80 ms 8148 KB Output is correct
3 Correct 137 ms 9672 KB Output is correct
4 Correct 85 ms 8132 KB Output is correct
5 Correct 89 ms 8128 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 63 ms 1584 KB Output is correct
12 Correct 1 ms 596 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10049 ms 5364 KB Output is correct
2 Correct 6746 ms 5188 KB Output is correct
3 Correct 11158 ms 5280 KB Output is correct
4 Correct 11053 ms 5284 KB Output is correct
5 Correct 9901 ms 5232 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Execution timed out 20020 ms 5240 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 16080 KB Output is correct
2 Correct 484 ms 15948 KB Output is correct
3 Correct 486 ms 16072 KB Output is correct
4 Correct 473 ms 16720 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9953 ms 5236 KB Output is correct
2 Correct 6289 ms 5192 KB Output is correct
3 Correct 10063 ms 5280 KB Output is correct
4 Correct 10049 ms 5280 KB Output is correct
5 Correct 9679 ms 5248 KB Output is correct
6 Correct 436 ms 15956 KB Output is correct
7 Correct 474 ms 15956 KB Output is correct
8 Correct 443 ms 15956 KB Output is correct
9 Correct 464 ms 16772 KB Output is correct
10 Correct 75 ms 8020 KB Output is correct
11 Correct 73 ms 8124 KB Output is correct
12 Correct 131 ms 9708 KB Output is correct
13 Correct 78 ms 8148 KB Output is correct
14 Correct 74 ms 8128 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 64 ms 1660 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Execution timed out 20035 ms 5272 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9695 ms 5236 KB Output is correct
2 Correct 6062 ms 5192 KB Output is correct
3 Correct 9662 ms 5276 KB Output is correct
4 Correct 9710 ms 5280 KB Output is correct
5 Correct 9545 ms 5256 KB Output is correct
6 Correct 437 ms 15956 KB Output is correct
7 Correct 487 ms 15948 KB Output is correct
8 Correct 442 ms 15956 KB Output is correct
9 Correct 470 ms 16732 KB Output is correct
10 Correct 73 ms 8120 KB Output is correct
11 Correct 73 ms 8148 KB Output is correct
12 Correct 131 ms 9664 KB Output is correct
13 Correct 73 ms 8128 KB Output is correct
14 Correct 87 ms 8128 KB Output is correct
15 Runtime error 3763 ms 262144 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -