oj.uz

Submission #1068993

# Submission time Handle Problem Language Result Execution time Memory
1068993 2024-08-21T14:08:23 Z sleepntsheep Wombats (IOI13_wombats) C++17
100 / 100
 6503 ms 185164 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;

#include "wombats.h"

#ifndef ROW
#define ROW 5000
#endif

#define COL 200

/* 256 Mb memory - 64 Million Ints
 - one matrix is 200x200 -> max 1600
 block + segtree
Memory - 200^2 * 2 * ceil(5000 / B)
Time Per update - [ 200 * 200 * B + lg[ceil(5000 / B)] * 200 * 200]
	there are 500 updates
Time for Init - [ 200 * 200 * B * ceil(5000 / B) + 200 * 200 * ceil(5000 / B) ]
		= [ 200 * 200 * 5000 + 200 * 200 * ceil(5000 / B) ]
1600 matrix - maybe B = 8, [5000 / B] = 625
*/

constexpr int B = 10;
int nb;

int r, c, h[5009][COL], v[5009][COL];

int L[9999], R[9999], a[1024][COL][COL];

void Unit(int blk) {
	for (int ii = 0; ii < c; ++ii) {
		static int dp[2][COL];
		/* find answer for (V1, V2) where V1 = ii */
		memset(dp[0], 63, sizeof dp[0]);
		dp[0][ii] = 0;
		int I = 0;
		for (int i = L[blk]; i <= R[blk]; ++i, I ^= 1) {
			if (i < r) {
				int pre = 1e9, suf = 1e9;
				for (int j = 0; j < c; ++j) {
					pre = min(pre, dp[I][j] - h[i][j]);
					dp[I][j] = min(dp[I][j], h[i][j] + pre);
				}
				for (int j = c - 1; j >= 0; --j) {
					suf = min(suf, dp[I][j] + h[i][j]);
					dp[I][j] = min(dp[I][j], suf - h[i][j]);
				}
			}
			for (int j = 0; j < c; ++j) dp[!I][j] = dp[I][j] + v[i][j];
		}
		for (int jj = 0; jj < c; ++jj)
			a[blk + nb][ii][jj] = dp[I][jj];
	}
}

void dnc(int l, int r, int optl, int optr, int *down, int *up, int mid[200][200]) {
	if (l > r) return;
	int m = (l + r) / 2;
	int opt = optl, val, val2;
	val = up[opt] + mid[opt][m];
	for (int k = optl + 1; k <= optr; ++k) {
		val2 = up[k] + mid[k][m];
		if (val2 < val) val = val2, opt = k;
	}
	down[m] = val;
	dnc(l, m - 1, optl, opt, down, up, mid);
	dnc(m + 1, r, opt, optr, down, up, mid);
}

void merg(int v) {
	for (int i = 0; i < c; ++i) for (int j = 0; j < c; ++j) a[v][i][j] = 1e9;
	for (int i = 0; i < c; ++i) 
		dnc(0, c - 1, 0, c - 1, a[v][i], a[2 * v][i], a[2 * v + 1]);
}

void init(int R, int C, int H[ROW][200], int V[ROW][200]) {
	r = R, c = C;
	for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j) v[i][j] = V[i][j];
	for (int i = 0 ; i < r; ++i) for (int j = 0; j + 1 < c; ++j) h[i][j + 1] = H[i][j] + h[i][j];

	nb = (r + B - 1) / B;
	while ((nb - 1) & nb) ++nb;

    	for (int i = 0; i < nb; ++i) {
    		L[i] = i * B;
    		::R[i] = min(r - 1, i * B + B - 1);
		Unit(i);
    	}
	for (int i = nb; --i; ) merg(i);
}

void update(int p) {
	Unit(p);
	for (p += nb; p /= 2; ) merg(p);
}

void changeH(int P, int Q, int W) {
	int dl = W - h[P][Q + 1] + h[P][Q];
	for (int j = Q + 1; j < c; ++j) h[P][j] += dl;
	update(P / B);
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	update(P / B);
}

int escape(int V1, int V2) { return a[1][V1][V2]; }

Compilation message

grader.c: In function 'int 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 4 ms 12636 KB Output is correct
2 Correct 4 ms 12632 KB Output is correct
3 Correct 38 ms 14420 KB Output is correct
4 Correct 5 ms 12636 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 40 ms 1560 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3248 KB Output is correct
2 Correct 151 ms 3164 KB Output is correct
3 Correct 160 ms 5112 KB Output is correct
4 Correct 170 ms 3376 KB Output is correct
5 Correct 154 ms 3164 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 657 ms 3176 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21084 KB Output is correct
2 Correct 10 ms 21320 KB Output is correct
3 Correct 10 ms 21340 KB Output is correct
4 Correct 39 ms 22536 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 3164 KB Output is correct
2 Correct 142 ms 3164 KB Output is correct
3 Correct 154 ms 3380 KB Output is correct
4 Correct 152 ms 3380 KB Output is correct
5 Correct 151 ms 3164 KB Output is correct
6 Correct 12 ms 21340 KB Output is correct
7 Correct 9 ms 21320 KB Output is correct
8 Correct 9 ms 21340 KB Output is correct
9 Correct 27 ms 22576 KB Output is correct
10 Correct 5 ms 12636 KB Output is correct
11 Correct 4 ms 12636 KB Output is correct
12 Correct 43 ms 15316 KB Output is correct
13 Correct 5 ms 12636 KB Output is correct
14 Correct 4 ms 12636 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 428 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 37 ms 4948 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 676 ms 3392 KB Output is correct
28 Correct 1502 ms 103124 KB Output is correct
29 Correct 1579 ms 100176 KB Output is correct
30 Correct 1585 ms 100944 KB Output is correct
31 Correct 1628 ms 104828 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 3164 KB Output is correct
2 Correct 152 ms 5208 KB Output is correct
3 Correct 155 ms 3160 KB Output is correct
4 Correct 153 ms 5208 KB Output is correct
5 Correct 156 ms 3164 KB Output is correct
6 Correct 11 ms 21084 KB Output is correct
7 Correct 10 ms 21084 KB Output is correct
8 Correct 10 ms 21188 KB Output is correct
9 Correct 30 ms 22624 KB Output is correct
10 Correct 5 ms 12632 KB Output is correct
11 Correct 6 ms 12636 KB Output is correct
12 Correct 43 ms 15208 KB Output is correct
13 Correct 5 ms 12472 KB Output is correct
14 Correct 6 ms 12636 KB Output is correct
15 Correct 2216 ms 180588 KB Output is correct
16 Correct 6503 ms 181660 KB Output is correct
17 Correct 0 ms 2392 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 600 KB Output is correct
27 Correct 44 ms 2896 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 683 ms 3368 KB Output is correct
30 Correct 1509 ms 104272 KB Output is correct
31 Correct 6152 ms 184512 KB Output is correct
32 Correct 6016 ms 184616 KB Output is correct
33 Correct 1575 ms 101040 KB Output is correct
34 Correct 6104 ms 181984 KB Output is correct
35 Correct 1506 ms 101500 KB Output is correct
36 Correct 6101 ms 181900 KB Output is correct
37 Correct 1659 ms 105644 KB Output is correct
38 Correct 6389 ms 185164 KB Output is correct
39 Correct 1 ms 2396 KB Output is correct
40 Correct 6140 ms 181248 KB Output is correct