Submission #635240

#	Time	Username	Problem	Language	Result	Execution time	Memory
635240		youngyojun	Wombats (IOI13_wombats)	C++17	100 / 100	6561 ms	113352 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

int A[5001][201], B[5001][201], C[5001][201];

int H, W, Q;

int fdi[201][201];
void f(int du[][201], int dd[][201], int dp[][201], int m) {
	for(int i = 1, r, ri; i <= W; i++) {
		r = INF;
		for(int j = 1, t; j <= W; j++) {
			t = du[i][j] + B[m][j] + dd[j][i];
			if(t < r) { r = t; ri = j; }
		}
		dp[i][i] = r; fdi[i][i] = ri;
	}
	for(int q = 1; q < W; q++) {
		for(int s = 1, e = q+1, r, ri, rie; e <= W; s++, e++) {
			r = INF; rie = fdi[s+1][e];
			for(int j = fdi[s][e-1], t; j <= rie; j++) {
				t = du[s][j] + B[m][j] + dd[j][e];
				if(t < r) { r = t; ri = j; }
			}
			dp[s][e] = r; fdi[s][e] = ri;
		}
		for(int s = q+1, e = 1, r, ri, rie; s <= W; s++, e++) {
			r = INF; rie = fdi[s][e+1];
			for(int j = fdi[s-1][e], t; j <= rie; j++) {
				t = du[s][j] + B[m][j] + dd[j][e];
				if(t < r) { r = t; ri = j; }
			}
			dp[s][e] = r; fdi[s][e] = ri;
		}
	}
}

int rdp[3][201][201];
void run(int dp[][201], int x) {
	for(int i = 1; i <= W; i++) {
		dp[i][i] = 0;
		for(int j = i+1; j <= W; j++)
			dp[i][j] = dp[j][i] = C[x][j]-C[x][i];
	}
}
void run(int dp[][201], int s, int e) {
	run(rdp[0], s);
	for(int i = s+1; i <= e; i++) {
		run(rdp[1], i);
		f(rdp[0], rdp[1], rdp[2], i-1);
		memcpy(rdp[0], rdp[2], 201*201*4);
	}
	memcpy(dp, rdp[0], 201*201*4);
}

struct NOD {
	int dp[201][201];
	NOD *pl = NULL, *pr = NULL;

	void cal(int s, int e) {
		if(e-s < 20) {
			run(dp, s, e);
			return;
		}
		int m = (s+e) >> 1;
		pl = new NOD(); pr = new NOD();
		pl -> cal(s, m); pr -> cal(m+1, e);
		f(pl->dp, pr->dp, dp, m);
	}
	void upd(int s, int e, int x) {
		if(e-s < 20) {
			run(dp, s, e);
			return;
		}
		int m = (s+e) >> 1;
		if(x <= m) pl -> upd(s, m, x);
		else pr -> upd(m+1, e, x);
		f(pl->dp, pr->dp, dp, m);
	}
} nod;

void init(int H, int W, int A[5000][200], int B[5000][200]) {
	::H = H; ::W = W;
	for(int i = 1; i <= H; i++) {
		for(int j = 1; j < W; j++) {
			int c = A[i-1][j-1];
			::A[i][j] = c;
			::C[i][j+1] = ::C[i][j] + c;
		}
	}
	for(int i = 1; i < H; i++)
		for(int j = 1; j <= W; j++)
			::B[i][j] = B[i-1][j-1];

	nod.cal(1, H);
}

void changeH(int a, int b, int c) {
	a++; b++;
	A[a][b] = c;
	for(int i = 1; i < W; i++)
		C[a][i+1] = C[a][i] + A[a][i];
	nod.upd(1, H, a);
}

void changeV(int a, int b, int c) {
	a++; b++;
	B[a][b] = c;
	nod.upd(1, H, a);
}

int escape(int a, int b) {
	return nod.dp[a+1][b+1];
}

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;
      |      ^~~
wombats.cpp: In function 'void f(int (*)[201], int (*)[201], int (*)[201], int)':
wombats.cpp:35:28: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |    dp[s][e] = r; fdi[s][e] = ri;
      |                  ~~~~~~~~~~^~~~
wombats.cpp:27:28: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |    dp[s][e] = r; fdi[s][e] = ri;
      |                  ~~~~~~~~~~^~~~
wombats.cpp:18:27: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |   dp[i][i] = r; fdi[i][i] = ri;
      |                 ~~~~~~~~~~^~~~

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