oj.uz

Submission #58707

# Submission time Handle Problem Language Result Execution time Memory
58707 2018-07-19T00:40:02 Z kingpig9 Wombats (IOI13_wombats) C++11
76 / 100
 6824 ms 263168 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5003;
const int MAXM = 203;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N, M;
int H[MAXN][MAXM], V[MAXN][MAXM];

struct node {
	int path[MAXM][MAXM];

	int* operator[] (int x) {
		return path[x];
	}
};

int opt[MAXN][MAXM];

node operator + (node a, node b) {
	node res;
	fillchar(res.path, 63);

	//opt[i - 1][j] <= opt[i][j] <= opt[i][j + 1]
	//this is the KEY OBSERVATION

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			if (res[0][i] > a[0][j] + b[j][i]) {
				res[0][i] = a[0][j] + b[j][i];
				opt[0][i] = j;
			}
		}
	}

	//ok now let's do this
	for (int i = 1; i < M; i++) {
		//res[i][j] compute
		//opt[i - 1][j] <= opt[i][j] <= opt[i][j + 1]
		//for this reason it is better to do it in decreasing j
		opt[i][M] = M - 1;
		for (int j = M - 1; j >= 0; j--) {
			for (int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
				if (res[i][j] > a[i][k] + b[k][j]) {
					res[i][j] = a[i][k] + b[k][j];
					opt[i][j] = k;
				}
			}
		}
	}
	return res;
}

struct segtree {
	//so after all we need 512 * 2 = 1024
	node tree[1 << 10];
	node tmp[10];

	void make (int cur, int a, int b) {
		for (int r = a; r < b; r++) {
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < M; j++) {
					tmp[r - a][i][j] = V[r][j] + abs(H[r][i] - H[r][j]);
				}
			}
		}

		tree[cur] = tmp[0];
		for (int i = 1; i < b - a; i++) {
			tree[cur] = tree[cur] + tmp[i];
		}
	}

	void update (int r, int cur, int lt, int rt) {
		if (rt - lt <= 10) {
			make(cur, lt, rt);
			return;
		}

		int mid = (lt + rt) / 2;
		if (r < mid) {
			update(r, 2 * cur, lt, mid);
		} else {
			update(r, 2 * cur + 1, mid, rt);
		}
		tree[cur] = tree[2 * cur] + tree[2 * cur + 1];
	}

	void init (int cur, int lt, int rt) {
		if (rt - lt <= 10) {
			make(cur, lt, rt);
			return;
		}

		int mid = (lt + rt) / 2;
		init(2 * cur, lt, mid);
		init(2 * cur + 1, mid, rt);
		tree[cur] = tree[2 * cur] + tree[2 * cur + 1];
	}
} seg;

void init (int nnn, int mmm, int hhh[5000][200], int vvv[5000][200]) {
	N = nnn;
	M = mmm;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M - 1; j++) {
			H[i][j + 1] = H[i][j] + hhh[i][j];
		}
	}
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			V[i][j] = vvv[i][j];
		}
	}

	//optimal paths never cross over each other!
	//KEY OBSERVATION!!!!
	seg.init(1, 0, N);
}

void changeH (int x, int y, int w) {
	int diff = w - (H[x][y + 1] - H[x][y]);
	for (int i = y + 1; i < M; i++) {
		H[x][i] += diff;
	}
	seg.update(x, 1, 0, N);
}

void changeV (int x, int y, int w) {
	V[x][y] = w;
	seg.update(x, 1, 0, N);
}

int escape (int v1, int v2) {
	return seg.tree[1][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 1094 ms 174408 KB Output is correct
2 Correct 1166 ms 174588 KB Output is correct
3 Correct 1252 ms 177372 KB Output is correct
4 Correct 1127 ms 177372 KB Output is correct
5 Correct 1109 ms 177372 KB Output is correct
6 Correct 4 ms 177372 KB Output is correct
7 Correct 4 ms 177372 KB Output is correct
8 Correct 3 ms 177372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 177372 KB Output is correct
2 Correct 3 ms 177372 KB Output is correct
3 Correct 4 ms 177372 KB Output is correct
4 Correct 6 ms 177372 KB Output is correct
5 Correct 6 ms 177372 KB Output is correct
6 Correct 6 ms 177372 KB Output is correct
7 Correct 6 ms 177372 KB Output is correct
8 Correct 5 ms 177372 KB Output is correct
9 Correct 6 ms 177372 KB Output is correct
10 Correct 5 ms 177372 KB Output is correct
11 Correct 103 ms 177372 KB Output is correct
12 Correct 7 ms 177372 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 177372 KB Output is correct
2 Correct 163 ms 177372 KB Output is correct
3 Correct 189 ms 177372 KB Output is correct
4 Correct 201 ms 177372 KB Output is correct
5 Correct 181 ms 177372 KB Output is correct
6 Correct 4 ms 177372 KB Output is correct
7 Correct 4 ms 177372 KB Output is correct
8 Correct 4 ms 177372 KB Output is correct
9 Correct 759 ms 177372 KB Output is correct
10 Correct 3 ms 177372 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1323 ms 186040 KB Output is correct
2 Correct 1145 ms 186224 KB Output is correct
3 Correct 1101 ms 186236 KB Output is correct
4 Correct 1091 ms 187816 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 187816 KB Output is correct
2 Correct 185 ms 187816 KB Output is correct
3 Correct 166 ms 187816 KB Output is correct
4 Correct 182 ms 187816 KB Output is correct
5 Correct 156 ms 187816 KB Output is correct
6 Correct 1126 ms 187816 KB Output is correct
7 Correct 1108 ms 187816 KB Output is correct
8 Correct 1135 ms 187816 KB Output is correct
9 Correct 1168 ms 188820 KB Output is correct
10 Correct 1082 ms 188820 KB Output is correct
11 Correct 1180 ms 188820 KB Output is correct
12 Correct 1230 ms 188820 KB Output is correct
13 Correct 1130 ms 188820 KB Output is correct
14 Correct 1183 ms 188820 KB Output is correct
15 Correct 4 ms 188820 KB Output is correct
16 Correct 4 ms 188820 KB Output is correct
17 Correct 4 ms 188820 KB Output is correct
18 Correct 6 ms 188820 KB Output is correct
19 Correct 6 ms 188820 KB Output is correct
20 Correct 6 ms 188820 KB Output is correct
21 Correct 6 ms 188820 KB Output is correct
22 Correct 7 ms 188820 KB Output is correct
23 Correct 6 ms 188820 KB Output is correct
24 Correct 6 ms 188820 KB Output is correct
25 Correct 152 ms 188820 KB Output is correct
26 Correct 6 ms 188820 KB Output is correct
27 Correct 750 ms 188820 KB Output is correct
28 Correct 2512 ms 196052 KB Output is correct
29 Correct 2280 ms 196528 KB Output is correct
30 Correct 2395 ms 200152 KB Output is correct
31 Correct 2529 ms 208568 KB Output is correct
32 Correct 5 ms 208568 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 208568 KB Output is correct
2 Correct 153 ms 208568 KB Output is correct
3 Correct 194 ms 208568 KB Output is correct
4 Correct 201 ms 208568 KB Output is correct
5 Correct 159 ms 208568 KB Output is correct
6 Correct 1079 ms 208568 KB Output is correct
7 Correct 1085 ms 208568 KB Output is correct
8 Correct 1040 ms 208568 KB Output is correct
9 Correct 1180 ms 208568 KB Output is correct
10 Correct 1043 ms 208568 KB Output is correct
11 Correct 1067 ms 208568 KB Output is correct
12 Correct 1260 ms 208568 KB Output is correct
13 Correct 1016 ms 208568 KB Output is correct
14 Correct 1112 ms 208568 KB Output is correct
15 Correct 2671 ms 220540 KB Output is correct
16 Correct 6824 ms 231288 KB Output is correct
17 Correct 4 ms 231288 KB Output is correct
18 Correct 3 ms 231288 KB Output is correct
19 Correct 4 ms 231288 KB Output is correct
20 Correct 9 ms 231288 KB Output is correct
21 Correct 6 ms 231288 KB Output is correct
22 Correct 5 ms 231288 KB Output is correct
23 Correct 5 ms 231288 KB Output is correct
24 Correct 6 ms 231288 KB Output is correct
25 Correct 6 ms 231288 KB Output is correct
26 Correct 7 ms 231288 KB Output is correct
27 Correct 89 ms 231288 KB Output is correct
28 Correct 6 ms 231288 KB Output is correct
29 Correct 671 ms 231288 KB Output is correct
30 Correct 2257 ms 234732 KB Output is correct
31 Correct 5623 ms 243716 KB Output is correct
32 Correct 5590 ms 251372 KB Output is correct
33 Correct 2366 ms 251372 KB Output is correct
34 Correct 5704 ms 258820 KB Output is correct
35 Correct 2243 ms 261228 KB Output is correct
36 Runtime error 5575 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.
37 Halted 0 ms 0 KB -