oj.uz

Submission #98095

# Submission time Handle Problem Language Result Execution time Memory
98095 2019-02-20T16:16:40 Z tincamatei Wombats (IOI13_wombats) C++14
28 / 100
 1041 ms 178808 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 <= 10)
		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 <= 10)
		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 Correct 946 ms 174584 KB Output is correct
2 Incorrect 1041 ms 174584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 157416 KB Output is correct
2 Correct 128 ms 157444 KB Output is correct
3 Correct 146 ms 157432 KB Output is correct
4 Correct 160 ms 157700 KB Output is correct
5 Correct 154 ms 157672 KB Output is correct
6 Correct 142 ms 157560 KB Output is correct
7 Correct 149 ms 157688 KB Output is correct
8 Correct 152 ms 157560 KB Output is correct
9 Correct 148 ms 157604 KB Output is correct
10 Correct 146 ms 157688 KB Output is correct
11 Correct 267 ms 158732 KB Output is correct
12 Correct 138 ms 157688 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 158624 KB Output is correct
2 Correct 270 ms 158584 KB Output is correct
3 Correct 374 ms 158636 KB Output is correct
4 Correct 342 ms 158728 KB Output is correct
5 Correct 332 ms 158584 KB Output is correct
6 Correct 134 ms 157304 KB Output is correct
7 Correct 138 ms 157408 KB Output is correct
8 Correct 129 ms 157416 KB Output is correct
9 Correct 824 ms 158584 KB Output is correct
10 Correct 133 ms 157432 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 960 ms 178672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 158584 KB Output is correct
2 Correct 295 ms 158592 KB Output is correct
3 Correct 330 ms 158628 KB Output is correct
4 Correct 312 ms 158456 KB Output is correct
5 Correct 322 ms 158536 KB Output is correct
6 Incorrect 999 ms 178452 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 158500 KB Output is correct
2 Correct 273 ms 158580 KB Output is correct
3 Correct 399 ms 158584 KB Output is correct
4 Correct 346 ms 158456 KB Output is correct
5 Correct 343 ms 158456 KB Output is correct
6 Incorrect 1014 ms 178808 KB Output isn't correct
7 Halted 0 ms 0 KB -