Submission #280395

#	Time	Username	Problem	Language	Result	Execution time	Memory
280395		Saboon	Wombats (IOI13_wombats)	C++14	12 / 100	213 ms	19712 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int T = 20;
int M, R, C, H[5000][200], V[5000][200];
int bl[255][200][200], dp[1026][200][200], opt[200][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 change(int id, int L, int R, int idx){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		for (int i = 0; i < C; i++)
			for (int j = 0; j < C; j++)
				dp[id][i][j] = bl[L][i][j];
		return;
	}
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, idx);
	change(2*id+1, mid, R, idx);
	for (int i = 0; i < C; i++){
		for (int j = C-1; j >= 0; j--){
			int lo = 0, hi = C-1;
			if (j+1 < C)
				hi = opt[i][j+1];
			if (i > 0)
				lo = opt[i-1][j];
			dp[idx][i][j] = inf;
			for (int x = lo; x <= hi; x++){
				if (dp[idx][i][j] > dp[2*id+0][i][x] + dp[2*id+1][x][j]){
					dp[idx][i][j] = dp[2*id+0][i][x] + dp[2*id+1][x][j];
					opt[i][j] = x;
				}
			}
		}
	}
}

void MakeAll(){
	for (int V1 = 0; V1 < C; 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];
		}
	}
}
 
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]){
	M = (r-1)/T + 1;
	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);
	for (int i = 0; i < M; i++)
		change(1, 0, M, i);	
}
 
void changeH(int P, int Q, int W){
	H[P][Q] = W;
	ChangeBlock(P/T);
	change(1, 0, M, P/T);
}
 
void changeV(int P, int Q, int W){
	V[P][Q] = W;
	ChangeBlock(P/T);
	change(1, 0, M, P/T);
}
 
int escape(int V1, int V2){
	return dp[1][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: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24