Submission #1247956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247956		gs12117	Wombats (IOI13_wombats)	C++20	100 / 100	16885 ms	192132 KiB

wombats

#include "wombats.h"
int n, m;
int ph[5130][210];
int pv[5130][210];
const int itsz = 256;
int tarr[210];
struct stnode {
	long long int arr[210][210];
	stnode operator+(const stnode& r)const {
		stnode res;
		for (int i = 0; i < m; i++) {
			tarr[i] = m - 1;
		}
		for (int i = m - 1; i >= 0; i--) {
			int larr = 0;
			for (int j = 0; j < m; j++) {
				int carr = -1;
				long long int cres = 1e18;
				for (int k = larr; k <= tarr[j]; k++) {
					long long int sres = arr[i][k] + r.arr[k][j];
					if (cres > sres) {
						cres = sres;
						carr = k;
					}
				}
				res.arr[i][j] = cres;
				tarr[j] = carr;
			}
		}
		return res;
	}
};
stnode st[520];
long long int dp[210][210];

void buildnode(int x) {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			dp[i][j] = 1e17;
		}
		dp[i][i] = 0;
	}
	for (int lv = x * 20; lv < x * 20 + 20; lv++) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m - 1; j++) {
				if (dp[i][j + 1] > dp[i][j] + ph[lv][j])dp[i][j + 1] = dp[i][j] + ph[lv][j];
			}
			for (int j = m - 2; j >= 0; j--) {
				if (dp[i][j] > dp[i][j + 1] + ph[lv][j])dp[i][j] = dp[i][j + 1] + ph[lv][j];
			}
			for (int j = 0; j < m; j++) {
				dp[i][j] += pv[lv][j];
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			st[x + itsz].arr[i][j] = dp[i][j];
		}
	}
}

void refreshnode(int x) {
	buildnode(x);
	x += itsz;
	x /= 2;
	while (x >= 1) {
		st[x] = st[x * 2] + st[x * 2 + 1];
		x /= 2;
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n = R;
	m = C;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m - 1; j++) {
			ph[i][j] = H[i][j];
		}
	}
	for (int i = n; i <= 5120; i++) {
		for (int j = 0; j < m - 1; j++) {
			ph[i][j] = 1e9;
		}
	}
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m; j++) {
			pv[i][j] = V[i][j];
		}
	}
	for (int i = n - 1; i <= 5120; i++) {
		for (int j = 0; j < m; j++) {
			pv[i][j] = 0;
		}
	}
	for (int i = 0; i < itsz; i++) {
		buildnode(i);
	}
	for (int i = itsz - 1; i >= 1; i--) {
		st[i] = st[i * 2] + st[i * 2 + 1];
	}
}

void changeH(int P, int Q, int W) {
	ph[P][Q] = W;
	refreshnode(P / 20);
}

void changeV(int P, int Q, int W) {
	pv[P][Q] = W;
	refreshnode(P / 20);
}

int escape(int V1, int V2) {
	return st[1].arr[V1][V2];
}

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