oj.uz

Submission #98090

# Submission time Handle Problem Language Result Execution time Memory
98090 2019-02-20T15:43:35 Z tincamatei Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 41760 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;
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;
	}
} dp[MAX_R / BUCK + 1];
 
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 updBuck(Matrix &x, int b) {
	initzero(x);
	for(int i = b * BUCK; i < (b + 1) * BUCK && i < R; ++i) {
		Matrix y;
		initrow(y, i);
		x = x * y;
	}
}
 
void calcrez() {
	initzero(rez);
	for(int i = 0; i < (R + BUCK - 1) / BUCK; ++i)
		rez = rez * dp[i];
}
 
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];
	}
 
	for(int i = 0; i < (R + BUCK - 1) / BUCK; ++i)
		updBuck(dp[i], i);
 
	calcrez();
}
 
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];
	int b = P / BUCK;
	updBuck(dp[b], b);
	calcrez();
}
 
void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	int b = P / BUCK;
	updBuck(dp[b], b);
	calcrez();
}
 
int escape(int V1, int V2) {
	return rez.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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3508 ms 27768 KB Output is correct
2 Correct 3533 ms 27904 KB Output is correct
3 Correct 3507 ms 29280 KB Output is correct
4 Correct 3488 ms 27896 KB Output is correct
5 Correct 3712 ms 27868 KB Output is correct
6 Correct 13 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Correct 12 ms 12160 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Correct 15 ms 12160 KB Output is correct
3 Correct 14 ms 12032 KB Output is correct
4 Correct 13 ms 12160 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 13 ms 12160 KB Output is correct
7 Correct 16 ms 12160 KB Output is correct
8 Correct 13 ms 12160 KB Output is correct
9 Correct 14 ms 12160 KB Output is correct
10 Correct 15 ms 12160 KB Output is correct
11 Correct 130 ms 13148 KB Output is correct
12 Correct 16 ms 12160 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 12596 KB Output is correct
2 Correct 843 ms 12544 KB Output is correct
3 Correct 1129 ms 12672 KB Output is correct
4 Correct 1071 ms 12792 KB Output is correct
5 Correct 1184 ms 12792 KB Output is correct
6 Correct 15 ms 12032 KB Output is correct
7 Correct 13 ms 12032 KB Output is correct
8 Correct 12 ms 12032 KB Output is correct
9 Correct 5347 ms 12668 KB Output is correct
10 Correct 17 ms 12160 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3849 ms 31856 KB Output is correct
2 Correct 3566 ms 31672 KB Output is correct
3 Correct 3549 ms 31868 KB Output is correct
4 Correct 3706 ms 32508 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 12724 KB Output is correct
2 Correct 894 ms 12664 KB Output is correct
3 Correct 1092 ms 12792 KB Output is correct
4 Correct 1004 ms 12756 KB Output is correct
5 Correct 1261 ms 12644 KB Output is correct
6 Correct 3635 ms 31840 KB Output is correct
7 Correct 3649 ms 31736 KB Output is correct
8 Correct 3520 ms 31736 KB Output is correct
9 Correct 3513 ms 33100 KB Output is correct
10 Correct 3417 ms 27896 KB Output is correct
11 Correct 3214 ms 27896 KB Output is correct
12 Correct 3402 ms 30444 KB Output is correct
13 Correct 3359 ms 27808 KB Output is correct
14 Correct 3610 ms 27804 KB Output is correct
15 Correct 14 ms 12160 KB Output is correct
16 Correct 12 ms 12032 KB Output is correct
17 Correct 13 ms 12032 KB Output is correct
18 Correct 15 ms 12160 KB Output is correct
19 Correct 12 ms 12160 KB Output is correct
20 Correct 16 ms 12200 KB Output is correct
21 Correct 13 ms 12288 KB Output is correct
22 Correct 14 ms 12160 KB Output is correct
23 Correct 14 ms 12160 KB Output is correct
24 Correct 14 ms 12160 KB Output is correct
25 Correct 80 ms 14556 KB Output is correct
26 Correct 13 ms 12032 KB Output is correct
27 Correct 4988 ms 12672 KB Output is correct
28 Correct 9672 ms 36056 KB Output is correct
29 Correct 10849 ms 32360 KB Output is correct
30 Correct 10964 ms 32324 KB Output is correct
31 Correct 10275 ms 37796 KB Output is correct
32 Correct 14 ms 12160 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 12636 KB Output is correct
2 Correct 1127 ms 12672 KB Output is correct
3 Correct 1166 ms 12800 KB Output is correct
4 Correct 1064 ms 12748 KB Output is correct
5 Correct 1311 ms 12680 KB Output is correct
6 Correct 3602 ms 31736 KB Output is correct
7 Correct 3593 ms 31736 KB Output is correct
8 Correct 3698 ms 31868 KB Output is correct
9 Correct 3579 ms 33208 KB Output is correct
10 Correct 3499 ms 27776 KB Output is correct
11 Correct 3650 ms 27896 KB Output is correct
12 Correct 3610 ms 30728 KB Output is correct
13 Correct 3532 ms 27740 KB Output is correct
14 Correct 3610 ms 27804 KB Output is correct
15 Correct 2585 ms 41760 KB Output is correct
16 Execution timed out 20060 ms 41468 KB Time limit exceeded
17 Halted 0 ms 0 KB -