Submission #389864

#	Time	Username	Problem	Language	Result	Execution time	Memory
389864		rainboy	Wombats (IOI13_wombats)	C11	55 / 100	20034 ms	33916 KiB

wombats

#include "wombats.h"
#include <string.h>

#define N	5000
#define M	100

int min(int a, int b) { return a < b ? a : b; }

int aa[N][M - 1], bb[N - 1][M], dp[M][M], n, m;

void solve() {
	int i, j, js;

	for (js = 0; js < m; js++) {
		int *dp_ = dp[js];

		dp_[js] = 0;
		for (j = js + 1; j < m; j++)
			dp_[j] = dp_[j - 1] + aa[0][j - 1];
		for (j = js - 1; j >= 0; j--)
			dp_[j] = dp_[j + 1] + aa[0][j];
		for (i = 1; i < n; i++) {
			for (j = 0; j < m; j++)
				dp_[j] += bb[i - 1][j];
			for (j = 1; j < m; j++)
				dp_[j] = min(dp_[j], dp_[j - 1] + aa[i][j - 1]); 
			for (j = m - 2; j >= 0; j--)
				dp_[j] = min(dp_[j], dp_[j + 1] + aa[i][j]); 
		}
	}
}

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]);
	solve();
}

void changeH(int i, int j, int w) {
	aa[i][j] = w;
	solve();
}

void changeV(int i, int j, int w) {
	bb[i][j] = w;
	solve();
}

int escape(int js, int jt) {
	return dp[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: 0 / 21
• Subtask 6: 0 / 24