oj.uz

Submission #437486

# Submission time Handle Problem Language Result Execution time Memory
437486 2021-06-26T11:26:10 Z denverjin Wombats (IOI13_wombats) C++14
100 / 100
 14037 ms 179896 KB 
#include "wombats.h"
#include <bits/stdc++.h>

#define eprintf(args...) fprintf(stderr, args)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

const int mxn = 1 << 13;
int R, C;
int H[5000][200];
int V[5000][200];

struct O_o {
	int l, r;
	int dp[200][200];

	O_o() { l = r = -1; memset(dp, 0x3f, sizeof(dp)); }
};

O_o operator + (const O_o &A, const O_o &B) {
	if (A.l == -1) return B;
	if (B.l == -1) return A;
	O_o ans;
	ans.l = A.l, ans.r = B.r;
	static int pr[205][205];
	rep(i, C) rep(j, C) pr[i][j] = -1;
	for (int delta = -(C - 1); delta <= (C - 1); ++ delta) {
		for (int a = 0; a < C; ++ a) {
			int b = a + delta;
			if (b >= 0 && b < C) {
				int L = b ? pr[a][b - 1] : 0;
				int R = a + 1 < C ? pr[a + 1][b] : C - 1;
				for (int c = L; c <= R; ++ c) {
					if (ans.dp[a][b] > A.dp[a][c] + B.dp[c][b]) {
						ans.dp[a][b] = A.dp[a][c] + B.dp[c][b];
						pr[a][b] = c;
					}
				}
			}
		}
	}
	return ans;
}

const int b = 4, B = 1 << b;

O_o S[mxn >> (b - 1)];

O_o get(int i) {
	if (i + 1 >= R) return O_o();
	O_o ans;
	ans.l = i; ans.r = i + 1;
	static int sum[2][200];
	rep(c, 2) {
		sum[c][0] = 0;
		rep(j, C - 1) sum[c][j + 1] = sum[c][j] + H[i + c][j];
	}
	for (int a = 0; a < C; ++ a) {
		int mn = 0x3f3f3f3f;
		for (int b = a; b < C; ++ b) {
			mn = std::min(mn, sum[0][b] - sum[0][a] + V[i][b] - sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn + sum[1][b]);
		}
		mn = 0x3f3f3f3f;
		for (int b = 0; b < C; ++ b) {
			if (b <= a) mn = std::min(mn, sum[0][a] - sum[0][b] + V[i][b] - sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn + sum[1][b]);
		}
		mn = 0x3f3f3f3f;
		for (int b = a; b >= 0; -- b) {
			mn = std::min(mn, sum[0][a] - sum[0][b] + V[i][b] + sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn - sum[1][b]);
		}
		mn = 0x3f3f3f3f;
		for (int b = C - 1; b >= 0; -- b) {
			if (b >= a) mn = std::min(mn, sum[0][b] - sum[0][a] + V[i][b] + sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn - sum[1][b]);
		}
	}
	return ans;
}

void update(int i) {
	O_o ans;
	for (int j = i; j < i + B; ++ j)
		ans = ans + get(j);
	S[(i >> b) + (mxn >> b)] = ans;
	for (int x = (i >> b) + (mxn >> b); x >>= 1; ) {
		S[x] = S[x << 1] + S[x << 1 | 1];
	}
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
	R = _R;
	C = _C;
	memcpy(H, _H, sizeof(H));
	memcpy(V, _V, sizeof(V));
	for (int i = 0; i << b < R; ++ i) update(i << b);
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	if (P && ((P - 1) >> b) != (P >> b)) update((P - 1) >> b << b);
	update(P >> b << b);
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	update(P >> b << b);
	if ((P >> b) != ((P + 1) >> b)) update((P + 1) >> b << b);
}

int escape(int V1, int V2) {
	return S[1].dp[V1][V2];
}

#ifdef DEBUG
#include "grader.c"
#endif

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 731 ms 172868 KB Output is correct
2 Correct 738 ms 172996 KB Output is correct
3 Correct 842 ms 174516 KB Output is correct
4 Correct 775 ms 173100 KB Output is correct
5 Correct 726 ms 172956 KB Output is correct
6 Correct 94 ms 169008 KB Output is correct
7 Correct 89 ms 169060 KB Output is correct
8 Correct 89 ms 168996 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 168980 KB Output is correct
2 Correct 87 ms 169076 KB Output is correct
3 Correct 97 ms 169164 KB Output is correct
4 Correct 90 ms 169028 KB Output is correct
5 Correct 89 ms 169052 KB Output is correct
6 Correct 91 ms 169084 KB Output is correct
7 Correct 92 ms 169036 KB Output is correct
8 Correct 93 ms 169088 KB Output is correct
9 Correct 90 ms 168996 KB Output is correct
10 Correct 97 ms 169028 KB Output is correct
11 Correct 183 ms 170072 KB Output is correct
12 Correct 92 ms 169044 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 169304 KB Output is correct
2 Correct 505 ms 169412 KB Output is correct
3 Correct 579 ms 169428 KB Output is correct
4 Correct 628 ms 169312 KB Output is correct
5 Correct 571 ms 169412 KB Output is correct
6 Correct 97 ms 169044 KB Output is correct
7 Correct 96 ms 169040 KB Output is correct
8 Correct 88 ms 168988 KB Output is correct
9 Correct 1991 ms 169312 KB Output is correct
10 Correct 96 ms 169024 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 176940 KB Output is correct
2 Correct 718 ms 176868 KB Output is correct
3 Correct 735 ms 176908 KB Output is correct
4 Correct 764 ms 177676 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 169312 KB Output is correct
2 Correct 461 ms 169304 KB Output is correct
3 Correct 532 ms 169300 KB Output is correct
4 Correct 547 ms 169300 KB Output is correct
5 Correct 562 ms 169300 KB Output is correct
6 Correct 716 ms 176876 KB Output is correct
7 Correct 723 ms 177004 KB Output is correct
8 Correct 752 ms 176880 KB Output is correct
9 Correct 770 ms 177724 KB Output is correct
10 Correct 717 ms 172972 KB Output is correct
11 Correct 718 ms 172972 KB Output is correct
12 Correct 841 ms 174576 KB Output is correct
13 Correct 730 ms 172976 KB Output is correct
14 Correct 752 ms 172972 KB Output is correct
15 Correct 97 ms 169012 KB Output is correct
16 Correct 92 ms 169112 KB Output is correct
17 Correct 87 ms 168948 KB Output is correct
18 Correct 96 ms 169028 KB Output is correct
19 Correct 94 ms 169092 KB Output is correct
20 Correct 94 ms 169024 KB Output is correct
21 Correct 96 ms 169064 KB Output is correct
22 Correct 91 ms 169100 KB Output is correct
23 Correct 95 ms 169040 KB Output is correct
24 Correct 93 ms 168996 KB Output is correct
25 Correct 178 ms 170056 KB Output is correct
26 Correct 97 ms 169032 KB Output is correct
27 Correct 1924 ms 169304 KB Output is correct
28 Correct 3440 ms 177452 KB Output is correct
29 Correct 3789 ms 176096 KB Output is correct
30 Correct 3741 ms 175796 KB Output is correct
31 Correct 3706 ms 178352 KB Output is correct
32 Correct 94 ms 169028 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 169312 KB Output is correct
2 Correct 474 ms 169308 KB Output is correct
3 Correct 532 ms 169308 KB Output is correct
4 Correct 607 ms 169304 KB Output is correct
5 Correct 563 ms 169300 KB Output is correct
6 Correct 709 ms 176920 KB Output is correct
7 Correct 758 ms 176876 KB Output is correct
8 Correct 737 ms 177096 KB Output is correct
9 Correct 794 ms 177768 KB Output is correct
10 Correct 718 ms 172972 KB Output is correct
11 Correct 768 ms 173044 KB Output is correct
12 Correct 841 ms 174532 KB Output is correct
13 Correct 769 ms 172912 KB Output is correct
14 Correct 713 ms 173088 KB Output is correct
15 Correct 4383 ms 177040 KB Output is correct
16 Correct 14037 ms 178672 KB Output is correct
17 Correct 91 ms 169032 KB Output is correct
18 Correct 95 ms 169048 KB Output is correct
19 Correct 96 ms 169020 KB Output is correct
20 Correct 94 ms 169028 KB Output is correct
21 Correct 96 ms 169136 KB Output is correct
22 Correct 93 ms 169068 KB Output is correct
23 Correct 91 ms 169168 KB Output is correct
24 Correct 92 ms 169072 KB Output is correct
25 Correct 99 ms 169052 KB Output is correct
26 Correct 87 ms 169156 KB Output is correct
27 Correct 174 ms 171432 KB Output is correct
28 Correct 103 ms 169028 KB Output is correct
29 Correct 1939 ms 169376 KB Output is correct
30 Correct 3548 ms 178876 KB Output is correct
31 Correct 10583 ms 178968 KB Output is correct
32 Correct 11511 ms 178996 KB Output is correct
33 Correct 3804 ms 177736 KB Output is correct
34 Correct 12597 ms 177664 KB Output is correct
35 Correct 3771 ms 177500 KB Output is correct
36 Correct 12307 ms 177564 KB Output is correct
37 Correct 3543 ms 179896 KB Output is correct
38 Correct 11900 ms 179628 KB Output is correct
39 Correct 95 ms 169008 KB Output is correct
40 Correct 12685 ms 177560 KB Output is correct