oj.uz

Submission #280273

# Submission time Handle Problem Language Result Execution time Memory
280273 2020-08-22T15:23:53 Z amoo_safar Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 110668 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];

void Merge(int A, int B, int C, int rw){
	memset(seg[A].dp, 31, sizeof seg[A].dp);
	for(int i = 0; i < c; i++)
		for(int j = 0; j < c; j++)
			for(int k = 0; k < c; k++)
				seg[A].dp[i][j] = min(seg[A].dp[i][j], seg[C].dp[i][k] + V[rw][k] + seg[B].dp[k][j]);
}

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 2978 ms 53564 KB Output is correct
2 Correct 3012 ms 53576 KB Output is correct
3 Correct 3172 ms 56344 KB Output is correct
4 Correct 3061 ms 53576 KB Output is correct
5 Correct 2961 ms 53504 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 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 1 ms 384 KB Output is correct
3 Correct 1 ms 512 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 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 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 87 ms 2808 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 1570 ms 2712 KB Output is correct
2 Correct 1486 ms 2692 KB Output is correct
3 Correct 1566 ms 2724 KB Output is correct
4 Correct 1578 ms 2724 KB Output is correct
5 Correct 1461 ms 2708 KB Output is correct
6 Correct 0 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 7308 ms 2716 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 3090 ms 61936 KB Output is correct
2 Correct 3098 ms 61944 KB Output is correct
3 Correct 3130 ms 61848 KB Output is correct
4 Correct 3241 ms 63224 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 2712 KB Output is correct
2 Correct 1441 ms 2692 KB Output is correct
3 Correct 1501 ms 2728 KB Output is correct
4 Correct 1450 ms 2724 KB Output is correct
5 Correct 1423 ms 2808 KB Output is correct
6 Correct 3174 ms 61840 KB Output is correct
7 Correct 3154 ms 61828 KB Output is correct
8 Correct 3123 ms 61844 KB Output is correct
9 Correct 3288 ms 63412 KB Output is correct
10 Correct 3010 ms 53624 KB Output is correct
11 Correct 2992 ms 53576 KB Output is correct
12 Correct 3139 ms 56392 KB Output is correct
13 Correct 3001 ms 53624 KB Output is correct
14 Correct 3003 ms 53624 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 416 KB Output is correct
17 Correct 1 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 448 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 512 KB Output is correct
25 Correct 87 ms 2808 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 7312 ms 2688 KB Output is correct
28 Execution timed out 20009 ms 86180 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1539 ms 2716 KB Output is correct
2 Correct 1506 ms 2688 KB Output is correct
3 Correct 1475 ms 2808 KB Output is correct
4 Correct 1448 ms 2688 KB Output is correct
5 Correct 1445 ms 2708 KB Output is correct
6 Correct 3106 ms 61840 KB Output is correct
7 Correct 3099 ms 61952 KB Output is correct
8 Correct 3125 ms 61968 KB Output is correct
9 Correct 3165 ms 63472 KB Output is correct
10 Correct 2957 ms 53560 KB Output is correct
11 Correct 3022 ms 53624 KB Output is correct
12 Correct 3082 ms 56344 KB Output is correct
13 Correct 3079 ms 53576 KB Output is correct
14 Correct 3113 ms 53572 KB Output is correct
15 Correct 19883 ms 110668 KB Output is correct
16 Execution timed out 20069 ms 110000 KB Time limit exceeded
17 Halted 0 ms 0 KB -