Submission #97528

#	Time	Username	Problem	Language	Result	Execution time	Memory
97528		tincamatei	Wombats (IOI13_wombats)	C++14	37 / 100	20084 ms	21540 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24