Submission #389955

#	Time	Username	Problem	Language	Result	Execution time	Memory
389955		rainboy	Wombats (IOI13_wombats)	C11	100 / 100	4681 ms	185276 KiB

wombats

#include "wombats.h"
#include <string.h>
 
#define N	5000
#define M	200
#define M_	10
#define N_	(1 << 9)
#define INF	0x3f3f3f3f
 
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
 
int aa[N][M - 1], bb[N - 1][M], n, m, st[N_ * 2][M][M];
 
void pul(int i) {	/* http://blog.brucemerry.org.za/2013/07/ioi-2013-day-1-analysis.html (Knuth's optimization) */
	static int jj2[M][M];
	int l = i << 1, r = l | 1, d, j1, j2, j3;
 
	for (j1 = 0; j1 < m; j1++)
		memset(st[i][j1], 0x3f, m * sizeof *st[i][j1]);
	for (d = m - 1; d >= -(m - 1); d--)
		for (j1 = max(-d, 0); j1 < m && (j3 = j1 + d) < m; j1++) {
			int jl = j1 == 0 ? 0 : jj2[j1 - 1][j3], jr = j3 + 1 == m ? m - 1 : jj2[j1][j3 + 1], j2_, d_;
 
			j2_ = -1, d_ = INF * 2 + 1;
			for (j2 = jl; j2 <= jr; j2++) {
				int d = st[l][j1][j2] + st[r][j2][j3];
 
				if (d_ > d)
					d_ = d, j2_ = j2;
			}
			st[i][j1][j3] = min(d_, INF), jj2[j1][j3] = j2_;
		}
}
 
void solve(int i_) {
	int l = i_ * M_, r = min((i_ + 1) * M_, n - 1), i, j, js;
 
	for (js = 0; js < m; js++) {
		int *dp = st[N_ + i_][js], x;
 
		if (l >= r)
			memset(dp, 0x3f, m * sizeof *dp), dp[js] = 0;
		else {
			dp[js] = 0;
			for (j = js + 1; j < m; j++)
				dp[j] = dp[j - 1] + aa[l][j - 1];
			for (j = js - 1; j >= 0; j--)
				dp[j] = dp[j + 1] + aa[l][j];
			for (i = l + 1; i <= r; i++) {
				for (j = 0; j < m; j++) {
					dp[j] += bb[i - 1][j];
					if ((i < r || i == n - 1) && j > 0 && dp[j] > (x = dp[j - 1] + aa[i][j - 1]))
						dp[j] = x;
				}
				if (i < r || i == n - 1)
					for (j = m - 2; j >= 0; j--)
						if (dp[j] > (x = dp[j + 1] + aa[i][j]))
							dp[j] = x;
			}
		}
	}
}
 
void init(int n_, int m_, int A[5000][200], int B[5000][200]) {
	int i;
 
	n = n_, m = m_;
	for (i = 0; i < n; i++)
		memcpy(aa[i], A[i], (m - 1) * sizeof *A[i]);
	for (i = 0; i < n - 1; i++)
		memcpy(bb[i], B[i], m * sizeof *B[i]);
	for (i = 0; i < N_; i++)
		solve(i);
	for (i = N_ - 1; i > 0; i--)
		pul(i);
}
 
void update(int i) {
	solve(i), i += N_;
	while (i > 1)
		pul(i >>= 1);
}
 
void changeH(int i, int j, int w) {
	aa[i][j] = w;
	update(i % M_ == 0 && i == n - 1 ? i / M_ - 1 : i / M_);
}
 
void changeV(int i, int j, int w) {
	bb[i][j] = w;
	update(i / M_);
}
 
int escape(int js, int jt) {
	return st[1][js][jt];
}

Compilation message (stderr)

grader.c: In function '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: 24 / 24