oj.uz

Submission #104920

# Submission time Handle Problem Language Result Execution time Memory
104920 2019-04-09T18:19:56 Z eriksuenderhauf Wombats (IOI13_wombats) C++11
28 / 100
 4112 ms 65912 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wombats.h"
//#include "grader.h"
using namespace std;
typedef long long int ll;
const int INF = 1e9 + 7;
const int MAXN = 20005;
const double eps = 1e-9;
int RW, C, root = 0, segSz = 1;
int h[5000][200], v[5000][200], L[MAXN], R[MAXN];
int dp[5000][200][200];

void merge(int cur) {
	for (int i = 0; i < C; i++)
		for (int j = 0; j < C; j++)
			dp[cur][i][j] = INF;
	for (int i = 0; i < C; i++) {
		for (int j = 0; j < C; j++) {
			for (int k = 0; k < C; k++) {
				dp[cur][i][j] = min(dp[cur][i][j], dp[L[cur]][i][k] + dp[R[cur]][k][j]);
			}
		}
	}
}

void init(int cur, int l, int r) {
	for (int i = 0; i < C; i++) {
		for (int j = 0; j < C; j++)
			dp[cur][i][j] = INF;
		dp[cur][i][i] = 0;
	}
	for (int i = 0; i < C; i++) {
		for (int j = i + 1; j < C; j++)
			dp[cur][i][j] = min(dp[cur][i][j], dp[cur][i][j - 1] + h[l][j - 1]);
		for (int j = i - 1; j > -1; j--)
			dp[cur][i][j] = min(dp[cur][i][j], dp[cur][i][j + 1] + h[l][j]);
	}
	for (int i = 0; i < C; i++)
		for (int j = 0; j < C; j++)
			dp[cur][i][j] += v[l][j];
}

void upd(int l, int r, int cur, int ind) {
	if (r < ind || ind < l) return;
	if (ind <= l && r <= ind) {
		init(cur, l, r);
		return;
	}
	int m = (l + r) / 2;
	upd(l, m, L[cur], ind);
	upd(m + 1, r, R[cur], ind);
	merge(cur);
}

void build(int l, int r, int &cur) {
	cur = segSz++;
	if (l == r) {
		init(cur, l, r);
		return;
	}
	int m = (l + r) / 2;
	build(l, m, L[cur]);
	build(m + 1, r, R[cur]);
	merge(cur);
}

void init(int R1, int C1, int H[5000][200], int V[5000][200]) {
	RW = R1, C = C1;
	for (int i = 0; i < RW; i++)
		for (int j = 0; j + 1 < C; j++)
			h[i][j] = H[i][j];
	for (int i = 0; i + 1 < RW; i++)
		for (int j = 0; j < C; j++)
			v[i][j] = V[i][j];
	build(0, RW - 1, root);
}

void changeH(int p, int q, int w) {
	h[p][q] = w;
	upd(0, RW - 1, root, p);
}

void changeV(int p, int q, int w) {
	v[p][q] = w;
	upd(0, RW - 1, root, p);
}

int escape(int a, int b) {
	return dp[root][a][b];
}

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 Runtime error 88 ms 47864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 1152 KB Output is correct
5 Correct 3 ms 1180 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1152 KB Output is correct
8 Correct 4 ms 1152 KB Output is correct
9 Correct 3 ms 1152 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 71 ms 3568 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 16944 KB Output is correct
2 Correct 958 ms 16888 KB Output is correct
3 Correct 959 ms 17080 KB Output is correct
4 Correct 883 ms 17104 KB Output is correct
5 Correct 873 ms 16988 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4112 ms 17144 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 65748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 16888 KB Output is correct
2 Correct 896 ms 16760 KB Output is correct
3 Correct 994 ms 17116 KB Output is correct
4 Correct 945 ms 17144 KB Output is correct
5 Correct 910 ms 17108 KB Output is correct
6 Runtime error 120 ms 65912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 932 ms 16924 KB Output is correct
2 Correct 906 ms 16772 KB Output is correct
3 Correct 893 ms 17276 KB Output is correct
4 Correct 904 ms 17104 KB Output is correct
5 Correct 802 ms 17008 KB Output is correct
6 Runtime error 103 ms 65660 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -