oj.uz

Submission #98093

# Submission time Handle Problem Language Result Execution time Memory
98093 2019-02-20T16:15:07 Z tincamatei Wombats (IOI13_wombats) C++14
12 / 100
 86 ms 10880 KB 
#include "wombats.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_C = 20;
const int MAX_R = 5000;
const int INF = 1000000000;
const int BUCK = 70;
 
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 19 ms 7040 KB Output is correct
2 Incorrect 19 ms 7040 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 4 ms 1920 KB Output is correct
2 Correct 4 ms 1920 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 5 ms 1920 KB Output is correct
5 Correct 4 ms 1920 KB Output is correct
6 Correct 4 ms 1920 KB Output is correct
7 Correct 5 ms 1920 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 3 ms 1920 KB Output is correct
10 Correct 5 ms 1920 KB Output is correct
11 Correct 86 ms 2936 KB Output is correct
12 Correct 4 ms 1920 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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