oj.uz

Submission #763405

# Submission time Handle Problem Language Result Execution time Memory
763405 2023-06-22T09:21:01 Z SanguineChameleon Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26084 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxN = 5e3 + 20;
const int maxM = 2e2 + 20;
int hor[5020][220];
int ver[5020][220];
int memo[220][220];
int tmp[5020][220];
int dp[5020][220];
int N, M;
 

void calc(int X) {
	int lt = 0;
	int rt = N - 1;
	for (X = 0; X < M; X++) {
		dp[lt][X] = 0;
		for (int i = X - 1; i >= 0; i--) {
			dp[lt][i] = dp[lt][i + 1] + hor[lt][i];
		}
		for (int i = X + 1; i < M; i++) {
			dp[lt][i] = dp[lt][i - 1] + hor[lt][i - 1];
		}
		for (int i = lt + 1; i <= rt; i++) {
			for (int j = 0; j < M; j++) {
				tmp[i][j] = dp[i - 1][j] + ver[i - 1][j];
				dp[i][j] = tmp[i][j];
			}
			int best = tmp[i][0];
			for (int j = 1; j < M; j++) {
				best = min(best + hor[i][j - 1], tmp[i][j]);
				dp[i][j] = min(dp[i][j], best);
			}
			best = tmp[i][M - 1];
			for (int j = M - 2; j >= 0; j--) {
				best = min(best + hor[i][j], tmp[i][j]);
				dp[i][j] = min(dp[i][j], best);
			}
		}
		for (int Y = 0; Y < M; Y++) {
			memo[X][Y] = dp[rt][Y];
		}
	}
}

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++) {
			hor[i][j] = H[i][j];
		}
	}
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			ver[i][j] = V[i][j];
		}
	}
	calc(-1);
}

void changeH(int P, int Q, int W) {
	hor[P][Q] = W;
	calc(-1);
}
 
void changeV(int P, int Q, int W) {
	ver[P][Q] = W;
	calc(-1);
}
 
 
int escape(int V1, int V2) {
	return memo[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 24 ms 17108 KB Output is correct
2 Correct 20 ms 17108 KB Output is correct
3 Correct 76 ms 18744 KB Output is correct
4 Correct 18 ms 17156 KB Output is correct
5 Correct 19 ms 17108 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 58 ms 1356 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 912 KB Output is correct
2 Correct 370 ms 912 KB Output is correct
3 Correct 374 ms 912 KB Output is correct
4 Correct 377 ms 916 KB Output is correct
5 Correct 364 ms 852 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1844 ms 912 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25360 KB Output is correct
2 Correct 75 ms 25348 KB Output is correct
3 Correct 75 ms 25300 KB Output is correct
4 Correct 104 ms 26032 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 1040 KB Output is correct
2 Correct 360 ms 916 KB Output is correct
3 Correct 376 ms 912 KB Output is correct
4 Correct 374 ms 932 KB Output is correct
5 Correct 368 ms 936 KB Output is correct
6 Correct 76 ms 25320 KB Output is correct
7 Correct 75 ms 25352 KB Output is correct
8 Correct 76 ms 25244 KB Output is correct
9 Correct 104 ms 26084 KB Output is correct
10 Correct 26 ms 17108 KB Output is correct
11 Correct 32 ms 17108 KB Output is correct
12 Correct 81 ms 18680 KB Output is correct
13 Correct 26 ms 17108 KB Output is correct
14 Correct 25 ms 17108 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 62 ms 1408 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1841 ms 912 KB Output is correct
28 Execution timed out 20032 ms 25548 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 916 KB Output is correct
2 Correct 367 ms 852 KB Output is correct
3 Correct 372 ms 928 KB Output is correct
4 Correct 374 ms 912 KB Output is correct
5 Correct 370 ms 912 KB Output is correct
6 Correct 76 ms 25416 KB Output is correct
7 Correct 74 ms 25352 KB Output is correct
8 Correct 72 ms 25300 KB Output is correct
9 Correct 104 ms 26068 KB Output is correct
10 Correct 25 ms 17036 KB Output is correct
11 Correct 26 ms 17036 KB Output is correct
12 Correct 81 ms 18728 KB Output is correct
13 Correct 30 ms 17156 KB Output is correct
14 Correct 26 ms 17160 KB Output is correct
15 Correct 3817 ms 25524 KB Output is correct
16 Execution timed out 20042 ms 25684 KB Time limit exceeded
17 Halted 0 ms 0 KB -