oj.uz

Submission #97528

# Submission time Handle Problem Language Result Execution time Memory
97528 2019-02-16T18:43:18 Z tincamatei Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 21540 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_R = 5000;
const int MAX_C = 200;
const int BUCK = 71;
const int INF = 1000000001;

int R, C;
int H[MAX_R][MAX_C], V[MAX_R][MAX_C];
int sp[MAX_R][MAX_C];
int buckPath[BUCK + 1][MAX_C][MAX_C];
int bestPath[MAX_C][MAX_C];
int aux[MAX_C];

// TODO: calcDp -> done
//       calcBestpath -> done
//       init
//       changeH
//       changeV
//       escape
//       la changeH de updatat si sp

void calcDp(int buck, int l, int r) {
	for(int j = 0; j < C; ++j)
		for(int k = 0; k < C; ++k)
			buckPath[buck][j][k] = INF;
	for(int j = 0; j < C; ++j)
		buckPath[buck][j][j] = 0;
	
	for(int i = r - 1; i >= l; --i) {
		// Incep in j si termin in k
		for(int j = 0; j < C; ++j) {
			int pref = INF;
			for(int k = 0; k < C; ++k)
				aux[k] = INF;

			for(int k = 0; k < C; ++k) {
				pref = min(pref, buckPath[buck][j][k] + V[i][k] - sp[i][k]);
				aux[k] = min(aux[k], pref + sp[i][k]);
			}
			
			pref = INF;
			for(int k = C - 1; k >= 0; --k) {
				pref = min(pref, buckPath[buck][j][k] + V[i][k] + sp[i][k]);
				aux[k] = min(aux[k], pref - sp[i][k]);
			}

			for(int k = 0; k < C; ++k)
				buckPath[buck][j][k] = aux[k];
		}
	}
}

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 < C; ++i)
		V[R - 1][i] = 0;
}

void changeH(int P, int Q, int W) {
	int buck = P / BUCK;
	H[P][Q] = W;
	for(int i = 1; i < C; ++i)
		sp[P][i] = sp[P][i - 1] + H[P][i - 1];
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
}

int escape(int V1, int V2) {
	calcDp(0, 0, R);
	return buckPath[0][V2][V1];
}

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;
      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:77:6: warning: unused variable 'buck' [-Wunused-variable]
  int buck = P / BUCK;
      ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16176 KB Output is correct
2 Correct 52 ms 16000 KB Output is correct
3 Correct 15439 ms 18972 KB Output is correct
4 Correct 59 ms 16000 KB Output is correct
5 Correct 53 ms 16000 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 20 ms 384 KB Output is correct
5 Correct 20 ms 512 KB Output is correct
6 Correct 21 ms 608 KB Output is correct
7 Correct 20 ms 384 KB Output is correct
8 Correct 20 ms 512 KB Output is correct
9 Correct 26 ms 384 KB Output is correct
10 Correct 22 ms 504 KB Output is correct
11 Correct 8972 ms 3024 KB Output is correct
12 Correct 19 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 896 KB Output is correct
2 Correct 510 ms 896 KB Output is correct
3 Correct 551 ms 896 KB Output is correct
4 Correct 483 ms 940 KB Output is correct
5 Correct 470 ms 956 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 454 ms 1024 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 20040 KB Output is correct
2 Correct 221 ms 20028 KB Output is correct
3 Correct 211 ms 20092 KB Output is correct
4 Execution timed out 20014 ms 21524 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 1052 KB Output is correct
2 Correct 554 ms 940 KB Output is correct
3 Correct 575 ms 896 KB Output is correct
4 Correct 506 ms 1016 KB Output is correct
5 Correct 579 ms 896 KB Output is correct
6 Correct 214 ms 20168 KB Output is correct
7 Correct 229 ms 19968 KB Output is correct
8 Correct 237 ms 20088 KB Output is correct
9 Execution timed out 20084 ms 21428 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 896 KB Output is correct
2 Correct 446 ms 896 KB Output is correct
3 Correct 477 ms 1020 KB Output is correct
4 Correct 521 ms 1016 KB Output is correct
5 Correct 462 ms 1016 KB Output is correct
6 Correct 208 ms 19968 KB Output is correct
7 Correct 232 ms 20088 KB Output is correct
8 Correct 249 ms 20048 KB Output is correct
9 Execution timed out 20076 ms 21540 KB Time limit exceeded
10 Halted 0 ms 0 KB -