oj.uz

Submission #280309

# Submission time Handle Problem Language Result Execution time Memory
280309 2020-08-22T15:45:40 Z amoo_safar Wombats (IOI13_wombats) C++17
100 / 100
 4140 ms 112888 KB 
#include "wombats.h"

#include <bits/stdc++.h>

using namespace std;

const int MR = 5010;
const int MC = 210;
const int BL = 20;
const int CBL = 256;
const int Inf = 1000000000;

int r, c;
int H[MR][MC], V[MR][MC], ps[MC];

struct node {
	int dp[MC][MC];
};
node seg[CBL << 1];

int opt[MC][MC];

void Merge(int A, int B, int C, int rw){
	memset(seg[A].dp, 31, sizeof seg[A].dp);
	int lc, rc, mn, nw, idx;
	for(int i = 0; i < c; i++){
		for(int j = c - 1; j >= 0; j--){
			lc = (i ? opt[i - 1][j] : 0);
			rc = (j == c - 1 ? c - 1 : opt[i][j + 1]);
			mn = seg[C].dp[i][lc] + V[rw][lc] + seg[B].dp[lc][j];
			idx = lc;
			for(int k = lc + 1; k <= rc; k++){
				nw = seg[C].dp[i][k] + V[rw][k] + seg[B].dp[k][j];
				if(nw < mn){
					mn = nw;
					idx = k;
				}
			}
			opt[i][j] = idx;
			seg[A].dp[i][j] = mn;
		}
	}
}

int tdp[BL][MC];

void BuildRow(int id, int ur, int dr){
	//cerr << "# " << ur << ' ' << dr << '\n';
	int row;
	for(int sc = 0; sc < c; sc ++){
		memset(tdp, 0, sizeof tdp);
		ps[0] = 0;
		for(int i = 1; i < c; i++) ps[i] = ps[i - 1] + H[dr][i - 1];
		
		for(int i = 0; i < c; i++) tdp[0][i] = abs(ps[i] - ps[sc]);

		for(int i = dr - 1; i >= ur; i--){
			row = dr - i;
			ps[0] = 0;
			for(int j = 1; j < c; j++) ps[j] = ps[j - 1] + H[i][j - 1];
			
			int res = Inf;
			for(int j = 0; j < c; j++){
				res = min(res, V[i][j] + tdp[row - 1][j] - ps[j]);
				tdp[row][j] = ps[j] + res;
			}
			res = Inf;
			for(int j = c - 1; j >= 0; j--){
				res = min(res, V[i][j] + tdp[row - 1][j] + ps[j]);
				tdp[row][j] = min(tdp[row][j], res - ps[j]);
			}
		}
		/*
		for(int i = 0; i < c; i++)
			for(int j = 0; j < c; j++)
				seg[id].dp[i][j] = abs(ps[i] - ps[j]); //min(seg[id].dp[i][j]);
		*/
		for(int i = 0; i < c; i++)
			seg[id].dp[sc][i] = tdp[dr - ur][i];
	}
}
void Build(int id, int L, int R){
	if(R - L <= BL){
		BuildRow(id, L, R - 1);
		return ;
	}
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid);
	Build(id << 1 | 1, mid, R);
	Merge(id, id << 1, id << 1 | 1, mid - 1);
}

void ReBuild(int id, int L, int R, int lq, int rq){
	if(rq < L || R <= rq) return ;
	if(lq < L || R <= lq) return ;
	if(R - L <= BL){
		BuildRow(id, L, R - 1);
		return ;
	}
	int mid = (L + R) >> 1;
	ReBuild(id << 1, L, mid, lq, rq);
	ReBuild(id << 1 | 1, mid, R, lq, rq);
	Merge(id, id << 1, id << 1 | 1, mid - 1);	
}

/*
void Build(){
	memset(dp, 0, sizeof dp);
	//fill(dp[R - 1], dp[R - 1] + C, 0);
	for(int i = R - 2; i >= 0; i--){
		ps[0] = 0;
		for(int j = 1; j < C; j++) ps[j] = ps[j - 1] + H[i][j - 1];
		int res = Inf;
		for(int j = 0; j < C; j++){
			res = min(res, V[i][j] + dp[i + 1][j] - ps[j]);
			dp[i][j] = ps[j] + res;
		}
		res = Inf;
		for(int j = C - 1; j >= 0; j--){
			res = min(res, V[i][j] + dp[i + 1][j] + ps[j]);
			dp[i][j] = res - ps[j];
		}
	}
}
*/
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
    /* ... */
    r = _R; 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 = 0; i < r - 1; i++)
    	for(int j = 0; j < c; j++)
    		V[i][j] = _V[i][j];   	
    Build(1, 0, r);
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;

	ReBuild(1, 0, r, P, P);
    /* ... */
}

void changeV(int P, int Q, int W){
	V[P][Q] = W;
	ReBuild(1, 0, r, P, P + 1);
	//Build(1, 0, r);
    /* ... */
}

int escape(int V1, int V2) {
    return seg[1].dp[V2][V1];
}

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 67 ms 53496 KB Output is correct
2 Correct 64 ms 53624 KB Output is correct
3 Correct 150 ms 55160 KB Output is correct
4 Correct 86 ms 53504 KB Output is correct
5 Correct 70 ms 53496 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 89 ms 1528 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 2688 KB Output is correct
2 Correct 78 ms 2688 KB Output is correct
3 Correct 96 ms 2688 KB Output is correct
4 Correct 110 ms 2688 KB Output is correct
5 Correct 106 ms 2688 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 387 ms 2840 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 61872 KB Output is correct
2 Correct 72 ms 61696 KB Output is correct
3 Correct 94 ms 61792 KB Output is correct
4 Correct 113 ms 62584 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 2688 KB Output is correct
2 Correct 77 ms 2688 KB Output is correct
3 Correct 98 ms 2724 KB Output is correct
4 Correct 90 ms 2688 KB Output is correct
5 Correct 95 ms 2688 KB Output is correct
6 Correct 68 ms 61688 KB Output is correct
7 Correct 69 ms 61804 KB Output is correct
8 Correct 87 ms 61688 KB Output is correct
9 Correct 115 ms 62584 KB Output is correct
10 Correct 65 ms 53496 KB Output is correct
11 Correct 61 ms 53624 KB Output is correct
12 Correct 150 ms 55172 KB Output is correct
13 Correct 80 ms 53632 KB Output is correct
14 Correct 69 ms 53544 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 416 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 436 KB Output is correct
25 Correct 87 ms 1400 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 412 ms 2808 KB Output is correct
28 Correct 1187 ms 82984 KB Output is correct
29 Correct 1107 ms 83448 KB Output is correct
30 Correct 1115 ms 83452 KB Output is correct
31 Correct 1239 ms 88352 KB Output is correct
32 Correct 1 ms 384 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 2688 KB Output is correct
2 Correct 81 ms 2688 KB Output is correct
3 Correct 94 ms 2808 KB Output is correct
4 Correct 92 ms 2688 KB Output is correct
5 Correct 89 ms 2688 KB Output is correct
6 Correct 72 ms 61688 KB Output is correct
7 Correct 70 ms 61724 KB Output is correct
8 Correct 86 ms 61824 KB Output is correct
9 Correct 116 ms 62584 KB Output is correct
10 Correct 78 ms 53504 KB Output is correct
11 Correct 73 ms 53504 KB Output is correct
12 Correct 155 ms 55288 KB Output is correct
13 Correct 80 ms 53504 KB Output is correct
14 Correct 66 ms 53496 KB Output is correct
15 Correct 1226 ms 103732 KB Output is correct
16 Correct 4140 ms 106692 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 512 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 89 ms 2936 KB Output is correct
28 Correct 1 ms 512 KB Output is correct
29 Correct 385 ms 2868 KB Output is correct
30 Correct 1143 ms 86776 KB Output is correct
31 Correct 3862 ms 112516 KB Output is correct
32 Correct 3931 ms 112048 KB Output is correct
33 Correct 1089 ms 83648 KB Output is correct
34 Correct 3592 ms 108764 KB Output is correct
35 Correct 1090 ms 83576 KB Output is correct
36 Correct 3818 ms 108812 KB Output is correct
37 Correct 1226 ms 88572 KB Output is correct
38 Correct 3910 ms 112888 KB Output is correct
39 Correct 1 ms 384 KB Output is correct
40 Correct 3768 ms 108848 KB Output is correct