oj.uz

Submission #287350

# Submission time Handle Problem Language Result Execution time Memory
287350 2020-08-31T16:13:54 Z Namnamseo Wombats (IOI13_wombats) C++17
100 / 100
 9676 ms 179308 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int (*eh)[200];
int (*ev)[200];

const int inf = 2e9;
#define BS 10

// *** TREE
int tree[1024][200][200];

int r, c;

void merge_row(int dp1[][200], int dp2[][200], int out[][200]){
	int opt[c][c];

	// big diagonal.
	out[0][c-1] = inf;
	for(int i=0; i<c; ++i){
		if(out[0][c-1] > dp1[0][i] + dp2[i][c-1])
			out[0][c-1] = dp1[0][i] + dp2[i][c-1],
			opt[0][c-1] = i;
	}

	for(int diff=2-c; diff<=c-1; ++diff){
		for(int j=0; j<c; ++j){
			int i=j+diff;
			if(i<0 || i>=c) continue;
			int lb=0, rb=c-1;
			if(i != 0)  lb=opt[i-1][j];
			if(j+1 < c) rb=opt[i][j+1];
			out[i][j]=inf;
			for(int k=lb; k<=rb; ++k){
				if(out[i][j] > dp1[i][k]+dp2[k][j]){
					out[i][j] =dp1[i][k]+dp2[k][j];
					opt[i][j]=k;
				}
			}
		}
	}
}

void row_dp(int dp[][200],int rn){
	// pref
	int pa[c], pb[c];
	pa[0]=0; for(int i=1; i<c; ++i) pa[i]=pa[i-1]+eh[rn  ][i-1];
	pb[0]=0; for(int i=1; i<c; ++i) pb[i]=pb[i-1]+eh[rn+1][i-1];

    for(int sp=0; sp<c; ++sp){
        for(int j=0; j<c; ++j) dp[sp][j] = abs(pa[sp]-pa[j]) + ev[rn][j];
        for(int j=1, cm=dp[sp][0]; j<c; ++j){
            cm+=eh[rn+1][j-1];
            dp[sp][j]=cm=min(cm, dp[sp][j]);
        }
        for(int j=c-2,cm=dp[sp][c-1]; 0<=j; --j){
            cm+=eh[rn+1][j];
            dp[sp][j]=cm=min(cm, dp[sp][j]);
        }
    }
}

void tree_calc_dp(int pos,int row_l, int row_r){
	auto bef=tree[pos];
	row_dp(bef, row_l);
	for(int i=row_l+1; i <= row_r; ++i){
		int tmp[c][200], buf[c][200];

		row_dp(tmp, i);
		merge_row(bef, tmp, buf);

		memcpy(bef, buf, c*200*4);
	}
}

void tree_init(int pos,int myl,int myr){
	if(myr-myl < BS) tree_calc_dp(pos, myl, myr);
	else {
		int mid=((myl+myr)>>1);
		tree_init(pos*2, myl, mid);
		tree_init(pos*2+1, mid+1, myr);
		merge_row(tree[pos*2], tree[pos*2+1], tree[pos]);
	}
}
// *** TREE END

void update(int upd_row,int pos,int myl,int myr){
	if(myr<upd_row || upd_row < myl) return;
	if(myr-myl < BS)
		tree_calc_dp(pos, myl, myr);
	else {
		int mid=(myl+myr)/2;
		update(upd_row, pos*2, myl, mid);
		update(upd_row, pos*2+1, mid+1, myr);
		merge_row(tree[pos*2], tree[pos*2+1], tree[pos]);
	}
}

int getNode(int upd_row,int pos,int myl,int myr){
	if(myr<upd_row || upd_row < myl) return 0;
	if(myr-myl < BS) return pos;
	int mid=(myl+myr)/2;
    return getNode(upd_row, pos*2, myl, mid) + getNode(upd_row, pos*2+1, mid+1, myr);
}

extern "C" {
void changeH(int P, int Q, int W) {
	eh[P][Q] = W;
	update(P, 1, 0, r-2);
	if(P>=1 && getNode(P-1,1,0,r-2) != getNode(P,1,0,r-2)) update(P-1, 1, 0, r-2);
}

void changeV(int P, int Q, int W) {
	ev[P][Q] = W;
	update(P, 1, 0, r-2);
}

int escape(int V1, int V2) {
    return tree[1][V1][V2];
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R; c = C;
	eh = H; ev = V;
	tree_init(1, 0, r-2);
}
}

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 8960 KB Output is correct
2 Correct 6 ms 9064 KB Output is correct
3 Correct 90 ms 11768 KB Output is correct
4 Correct 7 ms 9088 KB Output is correct
5 Correct 6 ms 9088 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 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 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 384 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 416 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 89 ms 2804 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 181 ms 3480 KB Output is correct
2 Correct 137 ms 3200 KB Output is correct
3 Correct 198 ms 3328 KB Output is correct
4 Correct 174 ms 3344 KB Output is correct
5 Correct 184 ms 3324 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 712 ms 3328 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 11 ms 13952 KB Output is correct
2 Correct 11 ms 14080 KB Output is correct
3 Correct 12 ms 13952 KB Output is correct
4 Correct 54 ms 15352 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 3328 KB Output is correct
2 Correct 140 ms 3200 KB Output is correct
3 Correct 192 ms 3328 KB Output is correct
4 Correct 172 ms 3348 KB Output is correct
5 Correct 186 ms 3448 KB Output is correct
6 Correct 11 ms 13952 KB Output is correct
7 Correct 11 ms 13952 KB Output is correct
8 Correct 12 ms 13952 KB Output is correct
9 Correct 53 ms 15352 KB Output is correct
10 Correct 7 ms 9088 KB Output is correct
11 Correct 6 ms 9088 KB Output is correct
12 Correct 91 ms 11936 KB Output is correct
13 Correct 7 ms 9088 KB Output is correct
14 Correct 6 ms 9088 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 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 384 KB Output is correct
21 Correct 1 ms 384 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 92 ms 2936 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 716 ms 3340 KB Output is correct
28 Correct 2179 ms 97016 KB Output is correct
29 Correct 2226 ms 95224 KB Output is correct
30 Correct 2189 ms 95224 KB Output is correct
31 Correct 2228 ms 98656 KB Output is correct
32 Correct 0 ms 384 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 3472 KB Output is correct
2 Correct 135 ms 3200 KB Output is correct
3 Correct 195 ms 3320 KB Output is correct
4 Correct 176 ms 3328 KB Output is correct
5 Correct 185 ms 3320 KB Output is correct
6 Correct 11 ms 13952 KB Output is correct
7 Correct 11 ms 13952 KB Output is correct
8 Correct 12 ms 14080 KB Output is correct
9 Correct 54 ms 15352 KB Output is correct
10 Correct 7 ms 9088 KB Output is correct
11 Correct 6 ms 9088 KB Output is correct
12 Correct 93 ms 11772 KB Output is correct
13 Correct 7 ms 9088 KB Output is correct
14 Correct 7 ms 9088 KB Output is correct
15 Correct 3497 ms 176120 KB Output is correct
16 Correct 9676 ms 179308 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 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 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 89 ms 2812 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 710 ms 3452 KB Output is correct
30 Correct 2206 ms 96632 KB Output is correct
31 Correct 8476 ms 177320 KB Output is correct
32 Correct 8564 ms 177416 KB Output is correct
33 Correct 2176 ms 95164 KB Output is correct
34 Correct 8340 ms 175540 KB Output is correct
35 Correct 2236 ms 94916 KB Output is correct
36 Correct 8503 ms 175244 KB Output is correct
37 Correct 2256 ms 98424 KB Output is correct
38 Correct 8841 ms 177788 KB Output is correct
39 Correct 0 ms 384 KB Output is correct
40 Correct 8584 ms 175680 KB Output is correct