oj.uz

Submission #98096

# Submission time Handle Problem Language Result Execution time Memory
98096 2019-02-20T16:19:11 Z tincamatei Wombats (IOI13_wombats) C++14
28 / 100
 735 ms 263168 KB 
#include "wombats.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_C = 200;
const int MAX_R = 5000;
const int INF = 1000000000;
 
int R, C;
int H[MAX_R][MAX_C], V[MAX_R][MAX_C];
int sp[MAX_R][MAX_C];
int a[MAX_C][MAX_C];
 
struct Matrix {
	int dp[MAX_C][MAX_C];
	Matrix() {
		for(int i = 0; i < MAX_C; ++i)
			for(int j = 0; j < MAX_C; ++j)
				dp[i][j] = INF;
	}
 
	Matrix operator* (const Matrix &x) const {
		Matrix rez;
		for(int i = 0; i < C; ++i) {
			for(int j = 0; j < C; ++j) {
				int dist = dp[i][j] + x.dp[j][i];
				if(dist < rez.dp[i][i]) {
					rez.dp[i][i] = dist;
					a[i][i] = j;
				}
			}
		}
 
		for(int d = 1; d < C; ++d) {
			for(int i = 0; i < C - d; ++i) {
				int j = i + d;
				int st, dr;
				st = a[i][j - 1];
				dr = a[i + 1][j];
				for(int k = st; k <= dr; ++k) {
					int dist = dp[i][k] + x.dp[k][j];
					if(dist < rez.dp[i][j]) {
						rez.dp[i][j] = dist;
						a[i][j] = k;
					}
				}
			}
 
			for(int i = d; i < C; ++i) {
				int j = i - d;
				int st, dr;
				st = a[i - 1][j];
				dr = a[i][j + 1];
				for(int k = st; k <= dr; ++k) {
					int dist = dp[i][k] + x.dp[k][j];
					if(dist < rez.dp[i][j]) {
						rez.dp[i][j] = dist;
						a[i][j] = k;
					}
				}
			}
		}
		return rez;
	}
} aint[1000];

Matrix rez;

void initzero(Matrix &x) {
	for(int i = 0; i < C; ++i)
		for(int j = 0; j < C; ++j)
			if(i == j)
				x.dp[i][j] = 0;
			else
				x.dp[i][j] = INF;
}
 
void initrow(Matrix &x, int r) {
	for(int i = 0; i < C; ++i)
		for(int j = 0; j < C; ++j)
			x.dp[i][j] = abs(sp[r][i] - sp[r][j]) + V[r][j];
}
 
void updRange(Matrix &x, int l, int r) {
	initzero(x);
	for(int i = l; i <= r; ++i) {
		Matrix y;
		initrow(y, i);
		x = x * y;
	}
}

void initSegTree(int l, int r, int nod = 1) {
	if(r - l + 1 <= 1)
		updRange(aint[nod], l, r);
	else {
		int mid = (l + r) / 2;
		initSegTree(l, mid, 2 * nod);
		initSegTree(mid + 1, r, 2 * nod + 1);
		aint[nod] = aint[2 * nod] * aint[2 * nod + 1];
	}
}

void updPoint(int poz, int l, int r, int nod = 1) {
	if(poz < l || r < poz) return;
	if(r - l + 1 <= 1)
		updRange(aint[nod], l, r);
	else {
		int mid = (l + r) / 2;
		updPoint(poz, l, mid, 2 * nod);
		updPoint(poz, mid + 1, r, 2 * nod + 1);
		aint[nod] = aint[2 * nod] * aint[2 * nod + 1];
	}
}

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; ++j) {
			H[i][j] = _H[i][j];
			V[i][j] = _V[i][j];
		}
 
	for(int i = 0; i < R; ++i) {
		sp[i][0] = 0;
		for(int j = 1; j < C; ++j)
			sp[i][j] = sp[i][j - 1] + H[i][j - 1];
	}
 
	initSegTree(0, R - 1);
}
 
void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	for(int i = 1; i < C; ++i)
		sp[P][i] = sp[P][i - 1] + H[P][i - 1];
	updPoint(P, 0, R - 1);
}
 
void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	updPoint(P, 0, R - 1);
}
 
int escape(int V1, int V2) {
	return aint[1].dp[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 Runtime error 440 ms 263168 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 135 ms 157668 KB Output is correct
2 Correct 139 ms 157652 KB Output is correct
3 Correct 159 ms 157560 KB Output is correct
4 Correct 145 ms 158328 KB Output is correct
5 Correct 144 ms 158272 KB Output is correct
6 Correct 139 ms 158432 KB Output is correct
7 Correct 134 ms 158200 KB Output is correct
8 Correct 147 ms 158304 KB Output is correct
9 Correct 163 ms 158200 KB Output is correct
10 Correct 137 ms 158328 KB Output is correct
11 Correct 212 ms 159352 KB Output is correct
12 Correct 141 ms 158200 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 159052 KB Output is correct
2 Correct 267 ms 158976 KB Output is correct
3 Correct 273 ms 158968 KB Output is correct
4 Correct 281 ms 158928 KB Output is correct
5 Correct 282 ms 159096 KB Output is correct
6 Correct 147 ms 157524 KB Output is correct
7 Correct 135 ms 157532 KB Output is correct
8 Correct 132 ms 157688 KB Output is correct
9 Correct 735 ms 159228 KB Output is correct
10 Correct 152 ms 157732 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 422 ms 263168 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 300 ms 159016 KB Output is correct
2 Correct 251 ms 158972 KB Output is correct
3 Correct 308 ms 159096 KB Output is correct
4 Correct 277 ms 159096 KB Output is correct
5 Correct 286 ms 158968 KB Output is correct
6 Runtime error 464 ms 263168 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 336 ms 158968 KB Output is correct
2 Correct 299 ms 158968 KB Output is correct
3 Correct 343 ms 158968 KB Output is correct
4 Correct 287 ms 158940 KB Output is correct
5 Correct 298 ms 158968 KB Output is correct
6 Runtime error 483 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -