oj.uz

Submission #60018

# Submission time Handle Problem Language Result Execution time Memory
60018 2018-07-23T12:26:48 Z aome Wombats (IOI13_wombats) C++14
100 / 100
 13143 ms 203220 KB 
#include "wombats.h"

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int R, C;
int sum[205];
int H[5005][205];
int V[5005][205];
int opt[205][205];

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

	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[205]) {
	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[1005];

	#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) {
				Node tmp = cal(j + 1);
				T[i] = merge(T[i], tmp, 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) {
				Node tmp = cal(j + 1);
				T[i] = merge(T[i], tmp, 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 829 ms 175096 KB Output is correct
2 Correct 941 ms 175400 KB Output is correct
3 Correct 952 ms 178148 KB Output is correct
4 Correct 895 ms 178148 KB Output is correct
5 Correct 882 ms 178148 KB Output is correct
6 Correct 141 ms 178148 KB Output is correct
7 Correct 136 ms 178148 KB Output is correct
8 Correct 160 ms 178148 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 178148 KB Output is correct
2 Correct 176 ms 178148 KB Output is correct
3 Correct 141 ms 178148 KB Output is correct
4 Correct 159 ms 178148 KB Output is correct
5 Correct 166 ms 178148 KB Output is correct
6 Correct 165 ms 178148 KB Output is correct
7 Correct 153 ms 178148 KB Output is correct
8 Correct 146 ms 178148 KB Output is correct
9 Correct 151 ms 178148 KB Output is correct
10 Correct 158 ms 178148 KB Output is correct
11 Correct 292 ms 178148 KB Output is correct
12 Correct 148 ms 178148 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 178148 KB Output is correct
2 Correct 439 ms 178148 KB Output is correct
3 Correct 499 ms 178148 KB Output is correct
4 Correct 508 ms 178148 KB Output is correct
5 Correct 466 ms 178148 KB Output is correct
6 Correct 164 ms 178148 KB Output is correct
7 Correct 136 ms 178148 KB Output is correct
8 Correct 176 ms 178148 KB Output is correct
9 Correct 1574 ms 178148 KB Output is correct
10 Correct 156 ms 178148 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 186724 KB Output is correct
2 Correct 869 ms 186772 KB Output is correct
3 Correct 897 ms 186924 KB Output is correct
4 Correct 973 ms 188352 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 188352 KB Output is correct
2 Correct 412 ms 188352 KB Output is correct
3 Correct 528 ms 188352 KB Output is correct
4 Correct 529 ms 188352 KB Output is correct
5 Correct 430 ms 188352 KB Output is correct
6 Correct 863 ms 188352 KB Output is correct
7 Correct 893 ms 188352 KB Output is correct
8 Correct 895 ms 188352 KB Output is correct
9 Correct 975 ms 189452 KB Output is correct
10 Correct 829 ms 189452 KB Output is correct
11 Correct 850 ms 189452 KB Output is correct
12 Correct 963 ms 189452 KB Output is correct
13 Correct 838 ms 189452 KB Output is correct
14 Correct 871 ms 189452 KB Output is correct
15 Correct 143 ms 189452 KB Output is correct
16 Correct 145 ms 189452 KB Output is correct
17 Correct 140 ms 189452 KB Output is correct
18 Correct 149 ms 189452 KB Output is correct
19 Correct 163 ms 189452 KB Output is correct
20 Correct 134 ms 189452 KB Output is correct
21 Correct 167 ms 189452 KB Output is correct
22 Correct 155 ms 189452 KB Output is correct
23 Correct 145 ms 189452 KB Output is correct
24 Correct 166 ms 189452 KB Output is correct
25 Correct 219 ms 189452 KB Output is correct
26 Correct 148 ms 189452 KB Output is correct
27 Correct 1419 ms 189452 KB Output is correct
28 Correct 3533 ms 190536 KB Output is correct
29 Correct 3235 ms 190536 KB Output is correct
30 Correct 3297 ms 190536 KB Output is correct
31 Correct 3387 ms 191576 KB Output is correct
32 Correct 132 ms 191576 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 191576 KB Output is correct
2 Correct 366 ms 191576 KB Output is correct
3 Correct 450 ms 191576 KB Output is correct
4 Correct 577 ms 191576 KB Output is correct
5 Correct 461 ms 191576 KB Output is correct
6 Correct 899 ms 191576 KB Output is correct
7 Correct 870 ms 191576 KB Output is correct
8 Correct 889 ms 191576 KB Output is correct
9 Correct 922 ms 191576 KB Output is correct
10 Correct 869 ms 191576 KB Output is correct
11 Correct 850 ms 191576 KB Output is correct
12 Correct 878 ms 191576 KB Output is correct
13 Correct 846 ms 191576 KB Output is correct
14 Correct 916 ms 191576 KB Output is correct
15 Correct 3562 ms 191576 KB Output is correct
16 Correct 13143 ms 191872 KB Output is correct
17 Correct 144 ms 191872 KB Output is correct
18 Correct 169 ms 191872 KB Output is correct
19 Correct 152 ms 191872 KB Output is correct
20 Correct 154 ms 191872 KB Output is correct
21 Correct 133 ms 191872 KB Output is correct
22 Correct 155 ms 191872 KB Output is correct
23 Correct 159 ms 191872 KB Output is correct
24 Correct 150 ms 191872 KB Output is correct
25 Correct 157 ms 191872 KB Output is correct
26 Correct 140 ms 191872 KB Output is correct
27 Correct 265 ms 191872 KB Output is correct
28 Correct 147 ms 191872 KB Output is correct
29 Correct 1478 ms 191872 KB Output is correct
30 Correct 3353 ms 191872 KB Output is correct
31 Correct 10407 ms 191872 KB Output is correct
32 Correct 10885 ms 191872 KB Output is correct
33 Correct 3304 ms 191872 KB Output is correct
34 Correct 11496 ms 191872 KB Output is correct
35 Correct 3449 ms 191872 KB Output is correct
36 Correct 11119 ms 191872 KB Output is correct
37 Correct 3731 ms 191872 KB Output is correct
38 Correct 11241 ms 199376 KB Output is correct
39 Correct 140 ms 199376 KB Output is correct
40 Correct 11096 ms 203220 KB Output is correct