oj.uz

답안 #1067848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067848 2024-08-21T04:33:48 Z sleepntsheep 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 24144 KB 
#pragma GCC optimize("O3,unroll-loops")
#include "wombats.h"
#include <cstdio>
#include <set>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

#ifndef ROW
#define ROW 5000
#endif

int r, c, h[ROW][100], v[ROW][100];
int ans_5[100][100], vis[100];


void calc_ii(int ii) {
	static int dp[2][100];
	/* find answer for (V1, V2) where V1 = ii */
	memset(dp[0], 63, sizeof dp[0]);
	dp[0][ii] = 0;

	int I = 0;
	for (int i = 0; i < r; ++i, I ^= 1) {
		static int pre[100], suf[100], ph[100]; /* annoying ahh math */ 
		ph[0] = 0;
		for (int j = 0; j + 1 < c; ++j)
			ph[j + 1] = ph[j] + h[i][j];

		pre[0] = dp[I][0];
		for (int j = 1; j < c; ++j) pre[j] = min(pre[j - 1], dp[I][j] - ph[j]);
		suf[c - 1] = dp[I][c - 1] + ph[c - 1];
		for (int j = c - 2; j >= 0; --j) suf[j] = min(suf[j + 1], dp[I][j] + ph[j]);

		for (int j = 0; j < c; ++j)
			dp[I][j] = min(ph[j] + pre[j], suf[j] - ph[j]);
		for (int j = 0; j < c; ++j)
			dp[!I][j] = dp[I][j] + v[i][j];
	}
	for (int jj = 0; jj < c; ++jj) ans_5[ii][jj] = dp[(r - 1) & 1][jj];
	vis[ii] = 1;
}


void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	for (int i = 0; i < 100; ++i) vis[i] = 0;
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	for (int i = 0; i < 100; ++i) vis[i] = 0;
}

void init(int R, int C, int H[ROW][200], int V[ROW][200]) {
	r = R, c = C;

	for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j)
		v[i][j] = V[i][j];
	for (int i = 0 ; i < r; ++i) for (int j = 0; j + 1 < c; ++j)
		h[i][j] = H[i][j];

	for (int i = 0; i < c; ++i) calc_ii(i);
}

int escape(int V1, int V2) {
	if (not vis[V1]) calc_ii(V1);
	return ans_5[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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9564 KB Output is correct
2 Correct 12 ms 9780 KB Output is correct
3 Correct 50 ms 11344 KB Output is correct
4 Correct 12 ms 9564 KB Output is correct
5 Correct 11 ms 9784 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6556 KB Output is correct
11 Correct 41 ms 7504 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6492 KB Output is correct
2 Correct 9 ms 6492 KB Output is correct
3 Correct 8 ms 6660 KB Output is correct
4 Correct 9 ms 6492 KB Output is correct
5 Correct 8 ms 6656 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 7 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 12124 KB Output is correct
2 Correct 59 ms 12372 KB Output is correct
3 Correct 61 ms 12376 KB Output is correct
4 Correct 77 ms 12960 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6492 KB Output is correct
2 Correct 8 ms 6492 KB Output is correct
3 Correct 9 ms 6492 KB Output is correct
4 Correct 8 ms 6492 KB Output is correct
5 Correct 8 ms 6656 KB Output is correct
6 Correct 59 ms 12124 KB Output is correct
7 Correct 62 ms 12124 KB Output is correct
8 Correct 65 ms 12124 KB Output is correct
9 Correct 78 ms 12880 KB Output is correct
10 Correct 12 ms 9560 KB Output is correct
11 Correct 12 ms 9780 KB Output is correct
12 Correct 46 ms 11308 KB Output is correct
13 Correct 13 ms 9564 KB Output is correct
14 Correct 12 ms 9776 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 37 ms 7532 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 7 ms 6660 KB Output is correct
28 Execution timed out 20093 ms 12196 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6488 KB Output is correct
2 Correct 8 ms 6488 KB Output is correct
3 Correct 8 ms 6664 KB Output is correct
4 Correct 8 ms 6668 KB Output is correct
5 Correct 9 ms 6492 KB Output is correct
6 Correct 59 ms 12124 KB Output is correct
7 Correct 63 ms 12124 KB Output is correct
8 Correct 60 ms 12124 KB Output is correct
9 Correct 82 ms 12892 KB Output is correct
10 Correct 12 ms 9564 KB Output is correct
11 Correct 12 ms 9560 KB Output is correct
12 Correct 46 ms 11232 KB Output is correct
13 Correct 12 ms 9776 KB Output is correct
14 Correct 12 ms 9564 KB Output is correct
15 Runtime error 3042 ms 24144 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -