oj.uz

Submission #389955

# Submission time Handle Problem Language Result Execution time Memory
389955 2021-04-14T23:40:59 Z rainboy Wombats (IOI13_wombats) C
100 / 100
 4681 ms 185276 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12468 KB Output is correct
2 Correct 6 ms 12492 KB Output is correct
3 Correct 84 ms 14020 KB Output is correct
4 Correct 6 ms 12492 KB Output is correct
5 Correct 6 ms 12492 KB Output is correct
6 Correct 2 ms 4684 KB Output is correct
7 Correct 2 ms 4684 KB Output is correct
8 Correct 2 ms 4684 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4684 KB Output is correct
2 Correct 2 ms 4684 KB Output is correct
3 Correct 2 ms 4684 KB Output is correct
4 Correct 11 ms 20044 KB Output is correct
5 Correct 12 ms 20044 KB Output is correct
6 Correct 11 ms 20080 KB Output is correct
7 Correct 11 ms 20068 KB Output is correct
8 Correct 11 ms 19264 KB Output is correct
9 Correct 11 ms 20044 KB Output is correct
10 Correct 11 ms 19324 KB Output is correct
11 Correct 90 ms 21060 KB Output is correct
12 Correct 11 ms 20044 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 84664 KB Output is correct
2 Correct 221 ms 83780 KB Output is correct
3 Correct 254 ms 84628 KB Output is correct
4 Correct 256 ms 84576 KB Output is correct
5 Correct 250 ms 83780 KB Output is correct
6 Correct 2 ms 4684 KB Output is correct
7 Correct 3 ms 4684 KB Output is correct
8 Correct 3 ms 4684 KB Output is correct
9 Correct 727 ms 84548 KB Output is correct
10 Correct 3 ms 7244 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21048 KB Output is correct
2 Correct 11 ms 21072 KB Output is correct
3 Correct 11 ms 21000 KB Output is correct
4 Correct 57 ms 21856 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 84548 KB Output is correct
2 Correct 225 ms 83752 KB Output is correct
3 Correct 252 ms 84676 KB Output is correct
4 Correct 250 ms 84632 KB Output is correct
5 Correct 252 ms 83868 KB Output is correct
6 Correct 13 ms 21120 KB Output is correct
7 Correct 12 ms 21068 KB Output is correct
8 Correct 12 ms 21092 KB Output is correct
9 Correct 51 ms 21828 KB Output is correct
10 Correct 6 ms 12492 KB Output is correct
11 Correct 7 ms 12492 KB Output is correct
12 Correct 85 ms 14016 KB Output is correct
13 Correct 7 ms 12516 KB Output is correct
14 Correct 6 ms 12492 KB Output is correct
15 Correct 2 ms 4684 KB Output is correct
16 Correct 2 ms 4684 KB Output is correct
17 Correct 2 ms 4684 KB Output is correct
18 Correct 11 ms 20112 KB Output is correct
19 Correct 12 ms 20044 KB Output is correct
20 Correct 12 ms 20024 KB Output is correct
21 Correct 11 ms 20044 KB Output is correct
22 Correct 11 ms 19276 KB Output is correct
23 Correct 12 ms 20048 KB Output is correct
24 Correct 10 ms 19276 KB Output is correct
25 Correct 105 ms 21020 KB Output is correct
26 Correct 12 ms 20068 KB Output is correct
27 Correct 724 ms 84664 KB Output is correct
28 Correct 1122 ms 100220 KB Output is correct
29 Correct 1240 ms 97480 KB Output is correct
30 Correct 1199 ms 97476 KB Output is correct
31 Correct 1232 ms 101304 KB Output is correct
32 Correct 3 ms 7244 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 84728 KB Output is correct
2 Correct 220 ms 83860 KB Output is correct
3 Correct 249 ms 84584 KB Output is correct
4 Correct 250 ms 84580 KB Output is correct
5 Correct 243 ms 83752 KB Output is correct
6 Correct 11 ms 21068 KB Output is correct
7 Correct 11 ms 21068 KB Output is correct
8 Correct 11 ms 21068 KB Output is correct
9 Correct 52 ms 21840 KB Output is correct
10 Correct 7 ms 12492 KB Output is correct
11 Correct 8 ms 12532 KB Output is correct
12 Correct 95 ms 14100 KB Output is correct
13 Correct 6 ms 12492 KB Output is correct
14 Correct 7 ms 12492 KB Output is correct
15 Correct 1075 ms 176112 KB Output is correct
16 Correct 4681 ms 178724 KB Output is correct
17 Correct 2 ms 4684 KB Output is correct
18 Correct 2 ms 4644 KB Output is correct
19 Correct 2 ms 4648 KB Output is correct
20 Correct 11 ms 20044 KB Output is correct
21 Correct 13 ms 20136 KB Output is correct
22 Correct 13 ms 20076 KB Output is correct
23 Correct 13 ms 20092 KB Output is correct
24 Correct 11 ms 19276 KB Output is correct
25 Correct 12 ms 20044 KB Output is correct
26 Correct 11 ms 19368 KB Output is correct
27 Correct 103 ms 22484 KB Output is correct
28 Correct 13 ms 20044 KB Output is correct
29 Correct 726 ms 84728 KB Output is correct
30 Correct 1117 ms 103968 KB Output is correct
31 Correct 4011 ms 184648 KB Output is correct
32 Correct 4061 ms 184624 KB Output is correct
33 Correct 1213 ms 101040 KB Output is correct
34 Correct 4350 ms 181256 KB Output is correct
35 Correct 1220 ms 101028 KB Output is correct
36 Correct 4303 ms 181192 KB Output is correct
37 Correct 1188 ms 105744 KB Output is correct
38 Correct 4237 ms 185276 KB Output is correct
39 Correct 3 ms 7208 KB Output is correct
40 Correct 4456 ms 181352 KB Output is correct