oj.uz

Submission #762166

# Submission time Handle Problem Language Result Execution time Memory
762166 2023-06-21T02:40:54 Z SanguineChameleon Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26716 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#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 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];
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			memo[i][j] = -1;
		}
	}
}

void changeH(int P, int Q, int W) {
	hor[P][Q] = W;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			memo[i][j] = -1;
		}
	}
}

void changeV(int P, int Q, int W) {
	ver[P][Q] = W;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			memo[i][j] = -1;
		}
	}
}

void calc(int X) {
	dp[0][X] = 0;
	for (int i = X - 1; i >= 0; i--) {
		dp[0][i] = dp[0][i + 1] + hor[0][i];
	}
	for (int i = X + 1; i < M; i++) {
		dp[0][i] = dp[0][i - 1] + hor[0][i - 1];
	}
	for (int i = 1; i < N; 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 i = 0; i < M; i++) {
		memo[X][i] = dp[N - 1][i];
	}
}

int escape(int V1, int V2) {
	if (memo[V1][V2] == -1) {
		calc(V1);
	}
	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 18 ms 17108 KB Output is correct
2 Correct 18 ms 17192 KB Output is correct
3 Correct 71 ms 19532 KB Output is correct
4 Correct 18 ms 17108 KB Output is correct
5 Correct 20 ms 17108 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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 6 ms 964 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 6 ms 936 KB Output is correct
5 Correct 7 ms 1016 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 4 ms 992 KB Output is correct
10 Correct 0 ms 308 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 25416 KB Output is correct
2 Correct 54 ms 25428 KB Output is correct
3 Correct 55 ms 25432 KB Output is correct
4 Correct 87 ms 26716 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 6 ms 980 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 6 ms 1012 KB Output is correct
6 Correct 54 ms 25420 KB Output is correct
7 Correct 55 ms 25428 KB Output is correct
8 Correct 56 ms 25424 KB Output is correct
9 Correct 82 ms 26696 KB Output is correct
10 Correct 18 ms 17176 KB Output is correct
11 Correct 19 ms 17188 KB Output is correct
12 Correct 72 ms 19556 KB Output is correct
13 Correct 18 ms 17108 KB Output is correct
14 Correct 18 ms 17184 KB Output is correct
15 Correct 1 ms 288 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 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 468 KB Output is correct
24 Correct 0 ms 468 KB Output is correct
25 Correct 56 ms 2252 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 4 ms 956 KB Output is correct
28 Execution timed out 20016 ms 25484 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 6 ms 852 KB Output is correct
3 Correct 6 ms 852 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 7 ms 932 KB Output is correct
6 Correct 54 ms 25352 KB Output is correct
7 Correct 55 ms 25300 KB Output is correct
8 Correct 54 ms 25376 KB Output is correct
9 Correct 83 ms 26128 KB Output is correct
10 Correct 19 ms 17160 KB Output is correct
11 Correct 23 ms 17160 KB Output is correct
12 Correct 70 ms 18692 KB Output is correct
13 Correct 18 ms 17108 KB Output is correct
14 Correct 19 ms 17160 KB Output is correct
15 Correct 162 ms 25588 KB Output is correct
16 Execution timed out 20093 ms 25724 KB Time limit exceeded
17 Halted 0 ms 0 KB -