Submission #280163

#	Time	Username	Problem	Language	Result	Execution time	Memory
280163		Saboon	Wombats (IOI13_wombats)	C++14	55 / 100	20096 ms	37140 KiB

wombats

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

void MakeAll(){
	memset(dp, 63, sizeof dp);
	for (int i = 0; i < C; i++)
		dp[0][i][i] = 0;
	for (int i = 0; i < R; i += T){
		for (int j = 0; j < C; j++)
			for (int k = 0; k < C; k++)
				for (int x = 0; x < C; x++)
					dp[1][j][k] = min(dp[1][j][k], dp[0][j][x] + bl[i/T][x][k]);
		for (int j = 0; j < C; j++)
			for (int k = 0; k < C; k++)
				dp[0][j][k] = dp[1][j][k], dp[1][j][k] = inf;
	}
}

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);
	MakeAll();
	return;
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	ChangeBlock(P/T);
	MakeAll();
}

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

int escape(int V1, int V2) {
	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: 0 / 21
• Subtask 6: 0 / 24