Submission #280211

#	Time	Username	Problem	Language	Result	Execution time	Memory
280211		Saboon	Wombats (IOI13_wombats)	C++14	76 / 100	20059 ms	29888 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int T = 100;
int R, C, H[5000][200], V[5000][200];
int bl[55][200][200], dp[2][200][200];
bool mark[200];

void calc(int l, int r, int lo, int hi, int block, int V1){
	if (l >= r)
		return;
	int m = (l+r) >> 1, opt = -1;
	dp[1][V1][m] = inf;
	for (int i = lo; i < hi; i++){
		if (dp[0][V1][i] + bl[block][i][m] < dp[1][V1][m]){
			opt = i;
			dp[1][V1][m] = dp[0][V1][i] + bl[block][i][m];
		}
	}
	calc(l, m, lo, opt+1, block, V1);
	calc(m+1, r, opt, hi, block, V1);
}

void MakeAll(int V1){
	for (int i = 0; i < C; i++)
		dp[0][V1][i] = bl[0][V1][i];
	for (int i = T; i < R; i += T){
		int block = i/T;
		calc(0, C, 0, C, block, V1);
		for (int j = 0; j < C; j++)
			dp[0][V1][j] = dp[1][V1][j];
	}
	mark[V1] = 1;
}

void ChangeBlock(int block){
	for (int j = 0; j < C; j++){
		for (int k = 0; k < C; k++)
			bl[block][j][k] = inf;
		bl[block][j][j] = 0;
		for (int k = j+1; k < C; k++)
			bl[block][j][k] = bl[block][j][k-1] + H[T*block][k-1];
		for (int k = j-1; k >= 0; k--)
			bl[block][j][k] = bl[block][j][k+1] + H[T*block][k];
		for (int k = 0; k < C; k++)
			bl[block][j][k] += V[T*block][k];
		for (int i = T*block+1; i < min(R, T*(block+1)); i++){
			for (int k = 1; k < C; k++)
				bl[block][j][k] = min(bl[block][j][k], bl[block][j][k-1] + H[i][k-1]);
			for (int k = C-2; k >= 0; k--)
				bl[block][j][k] = min(bl[block][j][k], bl[block][j][k+1] + H[i][k]);
			for (int k = 0; k < C; k++)
				bl[block][j][k] += V[i][k];
		}
	}
}

void init(int r, int c, int h[5000][200], int v[5000][200]){
	R = r, C = c;
	for (int i = 0; i < 5000; i++)
		for (int j = 0; j < 200; j++)
			H[i][j] = h[i][j], V[i][j] = v[i][j];
	for (int i = 0; i < R; i += T)
		ChangeBlock(i/T);
	return;
}

void changeH(int P, int Q, int W){
	H[P][Q] = W;
	ChangeBlock(P/T);
	memset(mark, 0, sizeof mark);
}

void changeV(int P, int Q, int W){
	V[P][Q] = W;
	ChangeBlock(P/T);
	memset(mark, 0, sizeof mark);
}

int escape(int V1, int V2){
	if (mark[V1])
		return dp[0][V1][V2];
	MakeAll(V1);
	return dp[0][V1][V2];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24