oj.uz

Submission #1068913

# Submission time Handle Problem Language Result Execution time Memory
1068913 2024-08-21T13:08:23 Z sleepntsheep Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 106724 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 = 20;
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 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) for (int j = 0; j < c; ++j)
		for (int k = 0; k < c; ++k)
			a[v][i][j] = min(a[v][i][j], a[2 * v][i][k] + a[2 * v + 1][k][j]);
}

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 3 ms 13916 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 44 ms 15320 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 6544 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 39 ms 3584 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 5908 KB Output is correct
2 Correct 733 ms 8776 KB Output is correct
3 Correct 863 ms 8772 KB Output is correct
4 Correct 853 ms 8792 KB Output is correct
5 Correct 888 ms 7212 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 3902 ms 3968 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20828 KB Output is correct
2 Correct 6 ms 20828 KB Output is correct
3 Correct 6 ms 20920 KB Output is correct
4 Correct 38 ms 22352 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 8540 KB Output is correct
2 Correct 786 ms 8536 KB Output is correct
3 Correct 873 ms 8772 KB Output is correct
4 Correct 868 ms 8772 KB Output is correct
5 Correct 879 ms 8792 KB Output is correct
6 Correct 8 ms 20828 KB Output is correct
7 Correct 6 ms 20924 KB Output is correct
8 Correct 7 ms 21084 KB Output is correct
9 Correct 28 ms 22360 KB Output is correct
10 Correct 4 ms 18012 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 41 ms 20812 KB Output is correct
13 Correct 4 ms 18012 KB Output is correct
14 Correct 4 ms 17936 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 0 ms 4444 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 43 ms 8788 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 3926 ms 8864 KB Output is correct
28 Correct 10212 ms 63724 KB Output is correct
29 Correct 11035 ms 63820 KB Output is correct
30 Correct 10909 ms 63828 KB Output is correct
31 Correct 11212 ms 66384 KB Output is correct
32 Correct 1 ms 6488 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 8848 KB Output is correct
2 Correct 740 ms 8844 KB Output is correct
3 Correct 853 ms 8856 KB Output is correct
4 Correct 884 ms 8792 KB Output is correct
5 Correct 889 ms 8796 KB Output is correct
6 Correct 7 ms 24920 KB Output is correct
7 Correct 7 ms 24924 KB Output is correct
8 Correct 7 ms 24924 KB Output is correct
9 Correct 35 ms 26316 KB Output is correct
10 Correct 4 ms 21848 KB Output is correct
11 Correct 4 ms 21848 KB Output is correct
12 Correct 39 ms 24664 KB Output is correct
13 Correct 4 ms 21852 KB Output is correct
14 Correct 4 ms 21852 KB Output is correct
15 Correct 6380 ms 106724 KB Output is correct
16 Execution timed out 20049 ms 105384 KB Time limit exceeded
17 Halted 0 ms 0 KB -