oj.uz

Submission #586682

# Submission time Handle Problem Language Result Execution time Memory
586682 2022-06-30T14:33:48 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];

bool vis[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});
			}

			memset(vis, 0, sizeof(vis));

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

				if(!vis[c]){
					vis[c] = true;

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

					if(c != m - 1){
						if(dist[lst][r][c] + h[r][c] < dist[lst][r][c + 1]){
							dist[lst][r][c + 1] = dist[lst][r][c] + 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 88 ms 8128 KB Output is correct
2 Correct 93 ms 8124 KB Output is correct
3 Correct 172 ms 9804 KB Output is correct
4 Correct 95 ms 8140 KB Output is correct
5 Correct 89 ms 8128 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 2 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 1 ms 596 KB Output is correct
11 Correct 68 ms 1612 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 10531 ms 5364 KB Output is correct
2 Correct 6226 ms 5276 KB Output is correct
3 Correct 11171 ms 5280 KB Output is correct
4 Correct 10611 ms 5284 KB Output is correct
5 Correct 10349 ms 5232 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Execution timed out 20043 ms 5272 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 15956 KB Output is correct
2 Correct 622 ms 15956 KB Output is correct
3 Correct 558 ms 15948 KB Output is correct
4 Correct 564 ms 16672 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10653 ms 5236 KB Output is correct
2 Correct 6221 ms 5200 KB Output is correct
3 Correct 11703 ms 5276 KB Output is correct
4 Correct 11552 ms 5280 KB Output is correct
5 Correct 10540 ms 5236 KB Output is correct
6 Correct 491 ms 15944 KB Output is correct
7 Correct 531 ms 15956 KB Output is correct
8 Correct 508 ms 16076 KB Output is correct
9 Correct 542 ms 16684 KB Output is correct
10 Correct 115 ms 8128 KB Output is correct
11 Correct 118 ms 8128 KB Output is correct
12 Correct 178 ms 9652 KB Output is correct
13 Correct 95 ms 8148 KB Output is correct
14 Correct 107 ms 8124 KB Output is correct
15 Correct 0 ms 224 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 2 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 2 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 62 ms 1612 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Execution timed out 20067 ms 5168 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13090 ms 5236 KB Output is correct
2 Correct 6383 ms 5188 KB Output is correct
3 Correct 10601 ms 5336 KB Output is correct
4 Correct 11877 ms 5280 KB Output is correct
5 Correct 10931 ms 5300 KB Output is correct
6 Correct 496 ms 15956 KB Output is correct
7 Correct 509 ms 15956 KB Output is correct
8 Correct 494 ms 15956 KB Output is correct
9 Correct 546 ms 16796 KB Output is correct
10 Correct 91 ms 8140 KB Output is correct
11 Correct 91 ms 8124 KB Output is correct
12 Correct 152 ms 9712 KB Output is correct
13 Correct 89 ms 8124 KB Output is correct
14 Correct 88 ms 8124 KB Output is correct
15 Runtime error 4409 ms 262144 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -