oj.uz

Submission #58709

# Submission time Handle Problem Language Result Execution time Memory
58709 2018-07-19T00:44:01 Z kingpig9 Wombats (IOI13_wombats) C++11
100 / 100
 9158 ms 207008 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];
	}

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

int opt[MAXN][MAXM];

node operator + (const node &a, const 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 595 ms 174072 KB Output is correct
2 Correct 585 ms 174072 KB Output is correct
3 Correct 711 ms 176972 KB Output is correct
4 Correct 615 ms 176972 KB Output is correct
5 Correct 580 ms 176972 KB Output is correct
6 Correct 3 ms 176972 KB Output is correct
7 Correct 3 ms 176972 KB Output is correct
8 Correct 3 ms 176972 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 176972 KB Output is correct
2 Correct 143 ms 176972 KB Output is correct
3 Correct 202 ms 176972 KB Output is correct
4 Correct 198 ms 176972 KB Output is correct
5 Correct 170 ms 176972 KB Output is correct
6 Correct 4 ms 176972 KB Output is correct
7 Correct 3 ms 176972 KB Output is correct
8 Correct 3 ms 176972 KB Output is correct
9 Correct 693 ms 176972 KB Output is correct
10 Correct 4 ms 176972 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 185472 KB Output is correct
2 Correct 593 ms 185500 KB Output is correct
3 Correct 632 ms 185748 KB Output is correct
4 Correct 701 ms 187028 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 187028 KB Output is correct
2 Correct 160 ms 187028 KB Output is correct
3 Correct 166 ms 187028 KB Output is correct
4 Correct 212 ms 187028 KB Output is correct
5 Correct 196 ms 187028 KB Output is correct
6 Correct 584 ms 187028 KB Output is correct
7 Correct 604 ms 187028 KB Output is correct
8 Correct 635 ms 187028 KB Output is correct
9 Correct 655 ms 188420 KB Output is correct
10 Correct 597 ms 188420 KB Output is correct
11 Correct 589 ms 188420 KB Output is correct
12 Correct 692 ms 188420 KB Output is correct
13 Correct 624 ms 188420 KB Output is correct
14 Correct 601 ms 188420 KB Output is correct
15 Correct 3 ms 188420 KB Output is correct
16 Correct 4 ms 188420 KB Output is correct
17 Correct 3 ms 188420 KB Output is correct
18 Correct 5 ms 188420 KB Output is correct
19 Correct 5 ms 188420 KB Output is correct
20 Correct 4 ms 188420 KB Output is correct
21 Correct 4 ms 188420 KB Output is correct
22 Correct 4 ms 188420 KB Output is correct
23 Correct 5 ms 188420 KB Output is correct
24 Correct 4 ms 188420 KB Output is correct
25 Correct 108 ms 188420 KB Output is correct
26 Correct 5 ms 188420 KB Output is correct
27 Correct 583 ms 188420 KB Output is correct
28 Correct 2253 ms 189744 KB Output is correct
29 Correct 2315 ms 189744 KB Output is correct
30 Correct 2214 ms 189744 KB Output is correct
31 Correct 2269 ms 190592 KB Output is correct
32 Correct 3 ms 190592 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 190592 KB Output is correct
2 Correct 148 ms 190592 KB Output is correct
3 Correct 165 ms 190592 KB Output is correct
4 Correct 193 ms 190592 KB Output is correct
5 Correct 160 ms 190592 KB Output is correct
6 Correct 579 ms 190592 KB Output is correct
7 Correct 604 ms 190592 KB Output is correct
8 Correct 603 ms 190592 KB Output is correct
9 Correct 647 ms 190592 KB Output is correct
10 Correct 572 ms 190592 KB Output is correct
11 Correct 574 ms 190592 KB Output is correct
12 Correct 708 ms 190592 KB Output is correct
13 Correct 580 ms 190592 KB Output is correct
14 Correct 563 ms 190592 KB Output is correct
15 Correct 3315 ms 190592 KB Output is correct
16 Correct 9158 ms 191736 KB Output is correct
17 Correct 4 ms 191736 KB Output is correct
18 Correct 3 ms 191736 KB Output is correct
19 Correct 5 ms 191736 KB Output is correct
20 Correct 5 ms 191736 KB Output is correct
21 Correct 5 ms 191736 KB Output is correct
22 Correct 5 ms 191736 KB Output is correct
23 Correct 5 ms 191736 KB Output is correct
24 Correct 2 ms 191736 KB Output is correct
25 Correct 5 ms 191736 KB Output is correct
26 Correct 5 ms 191736 KB Output is correct
27 Correct 194 ms 191736 KB Output is correct
28 Correct 5 ms 191736 KB Output is correct
29 Correct 780 ms 191736 KB Output is correct
30 Correct 2634 ms 191736 KB Output is correct
31 Correct 7757 ms 191736 KB Output is correct
32 Correct 7593 ms 191736 KB Output is correct
33 Correct 2306 ms 191736 KB Output is correct
34 Correct 7612 ms 191736 KB Output is correct
35 Correct 2419 ms 191736 KB Output is correct
36 Correct 7983 ms 191736 KB Output is correct
37 Correct 2545 ms 194988 KB Output is correct
38 Correct 8054 ms 203532 KB Output is correct
39 Correct 4 ms 203532 KB Output is correct
40 Correct 8276 ms 207008 KB Output is correct