oj.uz

Submission #60008

# Submission time Handle Problem Language Result Execution time Memory
60008 2018-07-23T12:09:38 Z aome Wombats (IOI13_wombats) C++14
0 / 100
 20000 ms 263172 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);
	}
};

Node a[205];

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[2005];

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

	void build(int i, int l, int r) {
		if (r - l <= 10) {
			T[i] = a[l] = cal(l);
			for (int j = l; j < r; ++j) {
				T[i] = merge(T[i], a[j + 1] = 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 <= 10) {
			T[i] = a[l];
			for (int j = l; j < r; ++j) {
				T[i] = merge(T[i], a[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, a[P] = cal(P), 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 17586 ms 263172 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 263172 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.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 706 ms 263172 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.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20089 ms 263172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 869 ms 263172 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.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 805 ms 263172 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.
2 Halted 0 ms 0 KB -