oj.uz

Submission #280293

# Submission time Handle Problem Language Result Execution time Memory
280293 2020-08-22T15:36:37 Z amoo_safar Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 103772 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 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;
	Build(1, 0, r);
    /* ... */
}

void changeV(int P, int Q, int W){
	V[P][Q] = W;
	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 3042 ms 53540 KB Output is correct
2 Correct 2988 ms 53544 KB Output is correct
3 Correct 3109 ms 55076 KB Output is correct
4 Correct 3046 ms 53544 KB Output is correct
5 Correct 2991 ms 53548 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 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 90 ms 1400 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 2716 KB Output is correct
2 Correct 515 ms 2808 KB Output is correct
3 Correct 535 ms 2724 KB Output is correct
4 Correct 550 ms 2688 KB Output is correct
5 Correct 559 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 0 ms 384 KB Output is correct
9 Correct 2590 ms 2728 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3074 ms 61796 KB Output is correct
2 Correct 3129 ms 61900 KB Output is correct
3 Correct 3199 ms 61896 KB Output is correct
4 Correct 3164 ms 62608 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 2808 KB Output is correct
2 Correct 522 ms 2708 KB Output is correct
3 Correct 574 ms 2688 KB Output is correct
4 Correct 581 ms 2724 KB Output is correct
5 Correct 557 ms 2716 KB Output is correct
6 Correct 3113 ms 61776 KB Output is correct
7 Correct 3136 ms 61772 KB Output is correct
8 Correct 3088 ms 61776 KB Output is correct
9 Correct 3161 ms 62856 KB Output is correct
10 Correct 2987 ms 53624 KB Output is correct
11 Correct 2936 ms 53624 KB Output is correct
12 Correct 3062 ms 55160 KB Output is correct
13 Correct 2979 ms 53496 KB Output is correct
14 Correct 2971 ms 53496 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 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 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 95 ms 1436 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 2639 ms 2728 KB Output is correct
28 Execution timed out 20093 ms 82692 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 2720 KB Output is correct
2 Correct 504 ms 2816 KB Output is correct
3 Correct 541 ms 2808 KB Output is correct
4 Correct 544 ms 2808 KB Output is correct
5 Correct 529 ms 2688 KB Output is correct
6 Correct 3103 ms 61820 KB Output is correct
7 Correct 3128 ms 61816 KB Output is correct
8 Correct 3108 ms 61892 KB Output is correct
9 Correct 3172 ms 62568 KB Output is correct
10 Correct 2989 ms 53540 KB Output is correct
11 Correct 3018 ms 53540 KB Output is correct
12 Correct 3073 ms 55080 KB Output is correct
13 Correct 2937 ms 53544 KB Output is correct
14 Correct 2985 ms 53544 KB Output is correct
15 Correct 4994 ms 103672 KB Output is correct
16 Execution timed out 20100 ms 103772 KB Time limit exceeded
17 Halted 0 ms 0 KB -