oj.uz

Submission #1068874

# Submission time Handle Problem Language Result Execution time Memory
1068874 2024-08-21T12:43:46 Z sleepntsheep Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 185820 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[1300][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 7 ms 65880 KB Output is correct
2 Correct 7 ms 65884 KB Output is correct
3 Correct 42 ms 67660 KB Output is correct
4 Correct 7 ms 65884 KB Output is correct
5 Correct 7 ms 67936 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 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 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 38 ms 7440 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 966 ms 10824 KB Output is correct
2 Correct 852 ms 10892 KB Output is correct
3 Correct 1006 ms 11092 KB Output is correct
4 Correct 1012 ms 10832 KB Output is correct
5 Correct 980 ms 10832 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 4460 ms 10908 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 61252 KB Output is correct
2 Correct 9 ms 61272 KB Output is correct
3 Correct 9 ms 63324 KB Output is correct
4 Correct 30 ms 66636 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 10840 KB Output is correct
2 Correct 890 ms 10892 KB Output is correct
3 Correct 1048 ms 10904 KB Output is correct
4 Correct 1113 ms 7224 KB Output is correct
5 Correct 1048 ms 5312 KB Output is correct
6 Correct 8 ms 23776 KB Output is correct
7 Correct 11 ms 69300 KB Output is correct
8 Correct 9 ms 27740 KB Output is correct
9 Correct 46 ms 54740 KB Output is correct
10 Correct 6 ms 30000 KB Output is correct
11 Correct 7 ms 30136 KB Output is correct
12 Correct 67 ms 68680 KB Output is correct
13 Correct 5 ms 13824 KB Output is correct
14 Correct 8 ms 66112 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 0 ms 2488 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 6488 KB Output is correct
25 Correct 43 ms 8840 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 4838 ms 3372 KB Output is correct
28 Correct 11342 ms 128212 KB Output is correct
29 Correct 12800 ms 121172 KB Output is correct
30 Correct 12648 ms 126292 KB Output is correct
31 Correct 12958 ms 123236 KB Output is correct
32 Correct 2 ms 6488 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1052 ms 10904 KB Output is correct
2 Correct 940 ms 3336 KB Output is correct
3 Correct 1073 ms 3384 KB Output is correct
4 Correct 1077 ms 3372 KB Output is correct
5 Correct 1057 ms 3356 KB Output is correct
6 Correct 17 ms 21344 KB Output is correct
7 Correct 14 ms 21340 KB Output is correct
8 Correct 12 ms 21340 KB Output is correct
9 Correct 31 ms 22608 KB Output is correct
10 Correct 10 ms 12636 KB Output is correct
11 Correct 6 ms 12636 KB Output is correct
12 Correct 44 ms 15444 KB Output is correct
13 Correct 8 ms 57948 KB Output is correct
14 Correct 7 ms 57948 KB Output is correct
15 Correct 10870 ms 185820 KB Output is correct
16 Execution timed out 20049 ms 185408 KB Time limit exceeded
17 Halted 0 ms 0 KB -