oj.uz

Submission #60015

# Submission time Handle Problem Language Result Execution time Memory
60015 2018-07-23T12:21:18 Z aome Wombats (IOI13_wombats) C++14
76 / 100
 10615 ms 263168 KB 
#include "wombats.h"

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int R, C;
int sum[200];
int H[5000][200];
int V[5000][200];
int opt[200][200];

struct Node {
	int d[200][200];

	Node() {
		memset(d, INF, sizeof d);
	}
};

bool upd(int &x, int y) {
	if (x > y) { x = y; return 1; }
	return 0;
}

Node merge(Node y, Node z, int cost[200]) {
	Node x;
	for (int i = 0; i < C; ++i) {
		for (int j = 0; j < C; ++j) {
			if (upd(x.d[i][0], y.d[i][j] + z.d[j][0] + cost[j])) opt[i][0] = j;
		}
	}
	for (int i = 0; i < C; ++i) {
		for (int j = 0; j < C; ++j) {
			if (upd(x.d[C - 1][i], y.d[C - 1][j] + z.d[j][i] + cost[j])) opt[C - 1][i] = j;
		}
	}
	for (int i = C - 2; i >= 0; --i) {
		for (int j = 1; j < C; ++j) {
			int l = opt[i][j - 1], r = opt[i + 1][j];
			for (int k = l; k <= r; ++k) {
				if (upd(x.d[i][j], y.d[i][k] + z.d[k][j] + cost[k])) opt[i][j] = k;
			}
		}
	}
	return x;
}

Node cal(int p) {
	Node x;
	sum[0] = 0;
	for (int i = 1; i < C; ++i) {
		sum[i] = sum[i - 1] + H[p][i - 1];
	}
	for (int i = 0; i < C; ++i) {
		for (int j = 0; j <= i; ++j) {
			x.d[i][j] = x.d[j][i] = sum[i] - sum[j];
		}
	}
	return x;
}

struct SegmentTree {
	Node T[1000];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		if (r - l <= 20) {
			T[i] = cal(l);
			for (int j = l; j < r; ++j) {
				T[i] = merge(T[i], cal(j + 1), V[j]);
			}
			return;
		}
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T[i] = merge(T[i << 1], T[i << 1 | 1], V[mid]);
	}

	void upd(int i, int l, int r, int p) {
		if (r - l <= 20) {
			T[i] = cal(l);
			for (int j = l; j < r; ++j) {
				T[i] = merge(T[i], cal(j + 1), V[j]);
			}
			return;
		}
		if (mid >= p) upd(i << 1, l, mid, p);
		else upd(i << 1 | 1, mid + 1, r, p);
		T[i] = merge(T[i << 1], T[i << 1 | 1], V[mid]);
	}

	#undef mid
} IT;

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
	R = _R, C = _C;
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < (C - 1); ++j) {
			H[i][j] = _H[i][j];
		}
	}
	for (int i = 0; i < (R - 1); ++i) {
		for (int j = 0; j < C; ++j) {
			V[i][j] = _V[i][j];
		}
	}
	IT.build(1, 0, R - 1);
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W, IT.upd(1, 0, R - 1, P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W, IT.upd(1, 0, R - 1, P);
}

int escape(int V1, int V2) {
    return IT.T[1].d[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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1632 ms 167900 KB Output is correct
2 Correct 1601 ms 168008 KB Output is correct
3 Correct 1680 ms 170752 KB Output is correct
4 Correct 1561 ms 170752 KB Output is correct
5 Correct 1640 ms 170752 KB Output is correct
6 Correct 125 ms 170752 KB Output is correct
7 Correct 127 ms 170752 KB Output is correct
8 Correct 127 ms 170752 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 170752 KB Output is correct
2 Correct 140 ms 170752 KB Output is correct
3 Correct 128 ms 170752 KB Output is correct
4 Correct 143 ms 170752 KB Output is correct
5 Correct 143 ms 170752 KB Output is correct
6 Correct 139 ms 170752 KB Output is correct
7 Correct 130 ms 170752 KB Output is correct
8 Correct 138 ms 170752 KB Output is correct
9 Correct 142 ms 170752 KB Output is correct
10 Correct 140 ms 170752 KB Output is correct
11 Correct 239 ms 170752 KB Output is correct
12 Correct 137 ms 170752 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 170752 KB Output is correct
2 Correct 411 ms 170752 KB Output is correct
3 Correct 440 ms 170752 KB Output is correct
4 Correct 538 ms 170752 KB Output is correct
5 Correct 473 ms 170752 KB Output is correct
6 Correct 151 ms 170752 KB Output is correct
7 Correct 141 ms 170752 KB Output is correct
8 Correct 145 ms 170752 KB Output is correct
9 Correct 1541 ms 170752 KB Output is correct
10 Correct 130 ms 170752 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1681 ms 179400 KB Output is correct
2 Correct 1561 ms 179400 KB Output is correct
3 Correct 1662 ms 179456 KB Output is correct
4 Correct 1848 ms 181064 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 181064 KB Output is correct
2 Correct 408 ms 181064 KB Output is correct
3 Correct 479 ms 181064 KB Output is correct
4 Correct 509 ms 181064 KB Output is correct
5 Correct 452 ms 181064 KB Output is correct
6 Correct 1543 ms 181064 KB Output is correct
7 Correct 1498 ms 181064 KB Output is correct
8 Correct 1577 ms 181064 KB Output is correct
9 Correct 1559 ms 182000 KB Output is correct
10 Correct 1480 ms 182000 KB Output is correct
11 Correct 1513 ms 182000 KB Output is correct
12 Correct 1808 ms 182000 KB Output is correct
13 Correct 1625 ms 182000 KB Output is correct
14 Correct 1498 ms 182000 KB Output is correct
15 Correct 133 ms 182000 KB Output is correct
16 Correct 134 ms 182000 KB Output is correct
17 Correct 131 ms 182000 KB Output is correct
18 Correct 124 ms 182000 KB Output is correct
19 Correct 128 ms 182000 KB Output is correct
20 Correct 130 ms 182000 KB Output is correct
21 Correct 134 ms 182000 KB Output is correct
22 Correct 157 ms 182000 KB Output is correct
23 Correct 141 ms 182000 KB Output is correct
24 Correct 126 ms 182000 KB Output is correct
25 Correct 219 ms 182000 KB Output is correct
26 Correct 135 ms 182000 KB Output is correct
27 Correct 1333 ms 182000 KB Output is correct
28 Correct 3774 ms 188672 KB Output is correct
29 Correct 3847 ms 189284 KB Output is correct
30 Correct 3537 ms 192656 KB Output is correct
31 Correct 3716 ms 201072 KB Output is correct
32 Correct 130 ms 201072 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 201072 KB Output is correct
2 Correct 441 ms 201072 KB Output is correct
3 Correct 433 ms 201072 KB Output is correct
4 Correct 493 ms 201072 KB Output is correct
5 Correct 487 ms 201072 KB Output is correct
6 Correct 1530 ms 201072 KB Output is correct
7 Correct 1630 ms 201072 KB Output is correct
8 Correct 1596 ms 201072 KB Output is correct
9 Correct 1658 ms 201544 KB Output is correct
10 Correct 1643 ms 201544 KB Output is correct
11 Correct 1517 ms 201544 KB Output is correct
12 Correct 1708 ms 201544 KB Output is correct
13 Correct 1590 ms 201544 KB Output is correct
14 Correct 1458 ms 201544 KB Output is correct
15 Correct 2925 ms 211620 KB Output is correct
16 Correct 10615 ms 222972 KB Output is correct
17 Correct 134 ms 222972 KB Output is correct
18 Correct 126 ms 222972 KB Output is correct
19 Correct 125 ms 222972 KB Output is correct
20 Correct 127 ms 222972 KB Output is correct
21 Correct 131 ms 222972 KB Output is correct
22 Correct 125 ms 222972 KB Output is correct
23 Correct 127 ms 222972 KB Output is correct
24 Correct 151 ms 222972 KB Output is correct
25 Correct 123 ms 222972 KB Output is correct
26 Correct 124 ms 222972 KB Output is correct
27 Correct 204 ms 222972 KB Output is correct
28 Correct 134 ms 222972 KB Output is correct
29 Correct 1712 ms 222972 KB Output is correct
30 Correct 3430 ms 226664 KB Output is correct
31 Correct 9425 ms 234812 KB Output is correct
32 Correct 10130 ms 242116 KB Output is correct
33 Correct 3575 ms 242536 KB Output is correct
34 Correct 9634 ms 249932 KB Output is correct
35 Correct 3462 ms 253020 KB Output is correct
36 Correct 9396 ms 260428 KB Output is correct
37 Runtime error 3319 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
38 Halted 0 ms 0 KB -