oj.uz

Submission #798496

# Submission time Handle Problem Language Result Execution time Memory
798496 2023-07-30T18:53:46 Z QwertyPi Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 112196 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;
const int R_MAX = 5000;
const int C_MAX = 200;
const int K = 10;
const int R_DIV_K_MUL_2 = 1024;
const int INF = 1 << 30;
int R, C, H[R_MAX][C_MAX], V[R_MAX][C_MAX];
int A[R_MAX / K][C_MAX][C_MAX];
int st[R_DIV_K_MUL_2][C_MAX][C_MAX];
bool chmin(int& x, int y){
	if(x > y){
		x = y; return true;
	}
	return false;
}


int DP[C_MAX][C_MAX];
void init(){
	for(int i = 0; i < C; i++) for(int j = 0; j < C; j++) DP[i][j] = i == j ? 0 : INF;
}

void process(int row){
	for(int i = 0; i < C; i++){
		for(int j = 0; j < C; j++){
			for(int k = j - 1; k >= 0; k--){
				if(!chmin(DP[i][k], DP[i][k + 1] + H[row][k])){
					break;
				}
			}
			for(int k = j + 1; k < C; k++){
				if(!chmin(DP[i][k], DP[i][k - 1] + H[row][k - 1])){
					break;
				}
			}
		}
	}
	for(int i = 0; i < C; i++){
		for(int j = 0; j < C; j++){
			DP[i][j] += V[row][j];
		}
	}
}

void st_merge(int v, int vl, int vr){
	for(int i = 0; i < C; i++) for(int j = 0; j < C; j++) st[v][i][j] = INF;
	for(int i = 0; i < C; i++) for(int j = 0; j < C; j++) for(int k = 0; k < C; k++) chmin(st[v][i][k], st[vl][i][j] + st[vr][j][k]);
}

void st_update(int p, int v, int l, int r){
	if(l == r){
		for(int i = 0; i < C; i++) for(int j = 0; j < C; j++) st[v][i][j] = DP[i][j];
		return;
	}
	int m = (l + r) / 2;
	if(p <= m) st_update(p, v * 2 + 1, l, m);
	else st_update(p, v * 2 + 2, m + 1, r);
	st_merge(v, v * 2 + 1, v * 2 + 2);
}

void recalc(int part = -1){
	if(part == -1){
		for(int p = 0; p < R / K; p++) recalc(p);
		return;
	}
	init();
	for(int r = part * K; r < (part + 1) * K; r++){
		process(r);
	}
	st_update(part, 0, 0, R / K - 1);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    ::R = (R + K - 1) / K * K, ::C = C;
    for(int i = 0; i < R; i++){
    	for(int j = 0; j < C - 1; j++){
    		::H[i][j] = H[i][j];
		}
	}
	for(int i = R; i < ::R; i++){
		for(int j = 0; j < C - 1; j++){
			::H[i][j] = INF;
		}
	}
	for(int i = 0; i < R - 1; i++){
		for(int j = 0; j < C; j++){
			::V[i][j] = V[i][j];
		}
	}
	recalc();
}

void changeH(int P, int Q, int W) {
	::H[P][Q] = W;
	recalc(P / K);
}

void changeV(int P, int Q, int W) {
	::V[P][Q] = W;
	recalc(P / K);
}

int escape(int V1, int V2) {
	return st[0][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 6 ms 12372 KB Output is correct
2 Correct 6 ms 12488 KB Output is correct
3 Correct 60 ms 15116 KB Output is correct
4 Correct 6 ms 12372 KB Output is correct
5 Correct 6 ms 12372 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 484 KB Output is correct
11 Correct 55 ms 2512 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 2352 KB Output is correct
2 Correct 475 ms 2220 KB Output is correct
3 Correct 442 ms 2360 KB Output is correct
4 Correct 437 ms 2356 KB Output is correct
5 Correct 454 ms 2344 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2306 ms 2348 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21076 KB Output is correct
2 Correct 9 ms 21048 KB Output is correct
3 Correct 10 ms 21104 KB Output is correct
4 Correct 37 ms 22420 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 2272 KB Output is correct
2 Correct 481 ms 2324 KB Output is correct
3 Correct 438 ms 2380 KB Output is correct
4 Correct 431 ms 2360 KB Output is correct
5 Correct 466 ms 2340 KB Output is correct
6 Correct 10 ms 20996 KB Output is correct
7 Correct 10 ms 21040 KB Output is correct
8 Correct 10 ms 21060 KB Output is correct
9 Correct 38 ms 22476 KB Output is correct
10 Correct 6 ms 12372 KB Output is correct
11 Correct 6 ms 12484 KB Output is correct
12 Correct 59 ms 15168 KB Output is correct
13 Correct 6 ms 12372 KB Output is correct
14 Correct 6 ms 12372 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 444 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 56 ms 2504 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2238 ms 2348 KB Output is correct
28 Correct 9978 ms 99572 KB Output is correct
29 Correct 8583 ms 84320 KB Output is correct
30 Correct 8626 ms 84464 KB Output is correct
31 Correct 9734 ms 103880 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 2352 KB Output is correct
2 Correct 460 ms 2328 KB Output is correct
3 Correct 444 ms 2352 KB Output is correct
4 Correct 426 ms 2348 KB Output is correct
5 Correct 481 ms 2340 KB Output is correct
6 Correct 10 ms 21072 KB Output is correct
7 Correct 10 ms 21076 KB Output is correct
8 Correct 10 ms 21032 KB Output is correct
9 Correct 38 ms 22360 KB Output is correct
10 Correct 6 ms 12372 KB Output is correct
11 Correct 6 ms 12444 KB Output is correct
12 Correct 64 ms 15112 KB Output is correct
13 Correct 6 ms 12372 KB Output is correct
14 Correct 6 ms 12364 KB Output is correct
15 Execution timed out 20068 ms 112196 KB Time limit exceeded
16 Halted 0 ms 0 KB -