oj.uz

Submission #287211

# Submission time Handle Problem Language Result Execution time Memory
287211 2020-08-31T13:47:23 Z TMJN Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26872 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int bucket_size=1000;
int H,W,K[200][200][5],A[5100][200],B[5100][200],L[200][200];

void update(int x){
	int T[200];
	for(int i=0;i<W;i++){
		for(int j=0;j<W;j++){
			T[j]=0xE869120;
		}
		T[i]=0;
		for(int j=bucket_size*x;j<(bucket_size)*(x+1)&&j<H;j++){
			for(int k=0;k<W-1;k++){
				T[k+1]=min(T[k+1],T[k]+A[j][k]);
			}
			for(int k=W-2;k>=0;k--){
				T[k]=min(T[k],T[k+1]+A[j][k]);
			}
			for(int k=0;k<W;k++){
				T[k]+=B[j][k];
			}
		}
		for(int j=0;j<W;j++){
			K[i][j][x]=T[j];
		}
	}
}

void update_whole(){
	for(int i=0;i<W;i++){
		for(int j=0;j<W;j++){
			L[i][j]=K[i][j][0];
		}
	}
	for(int i=1;i*bucket_size<H;i++){
		for(int j=0;j<W;j++){
			int T[200];
			for(int k=0;k<W;k++){
				T[k]=0xE869120;
				for(int l=0;l<W;l++){
					T[k]=min(T[k],L[j][l]+K[l][k][i]);
				}
			}
			for(int k=0;k<W;k++){
				L[j][k]=T[k];
			}
		}
	}
}

void init(int R, int C, int h[5000][200], int v[5000][200]) {
    H=R;
    W=C;
    for(int i=0;i<H;i++){
		for(int j=0;j<W-1;j++){
			A[i][j]=h[i][j];
		}
	}
	for(int i=0;i<H-1;i++){
		for(int j=0;j<W;j++){
			B[i][j]=v[i][j];
		}
	}
	for(int i=0;i*bucket_size<H;i++){
		update(i);
	}
	update_whole();
}

void changeH(int P, int Q, int W) {
	A[P][Q]=W;
	update(P/bucket_size);
	update_whole();
}

void changeV(int P, int Q, int W) {
    B[P][Q]=W;
    update(P/bucket_size);
    update_whole();
}

int escape(int V1, int V2) {
	return L[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 7 ms 8192 KB Output is correct
2 Correct 7 ms 8192 KB Output is correct
3 Correct 94 ms 11000 KB Output is correct
4 Correct 7 ms 8192 KB Output is correct
5 Correct 7 ms 8192 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 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 88 ms 2812 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 648 ms 1412 KB Output is correct
2 Correct 630 ms 1276 KB Output is correct
3 Correct 652 ms 1272 KB Output is correct
4 Correct 647 ms 1272 KB Output is correct
5 Correct 635 ms 1272 KB Output is correct
6 Correct 1 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 3207 ms 1272 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 22 ms 16128 KB Output is correct
2 Correct 23 ms 16128 KB Output is correct
3 Correct 23 ms 16128 KB Output is correct
4 Correct 66 ms 17400 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 1256 KB Output is correct
2 Correct 634 ms 1152 KB Output is correct
3 Correct 652 ms 1272 KB Output is correct
4 Correct 649 ms 1260 KB Output is correct
5 Correct 640 ms 1152 KB Output is correct
6 Correct 23 ms 16128 KB Output is correct
7 Correct 22 ms 16000 KB Output is correct
8 Correct 22 ms 16128 KB Output is correct
9 Correct 67 ms 17400 KB Output is correct
10 Correct 7 ms 8192 KB Output is correct
11 Correct 7 ms 8192 KB Output is correct
12 Correct 97 ms 11000 KB Output is correct
13 Correct 7 ms 8192 KB Output is correct
14 Correct 7 ms 8192 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 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 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 512 KB Output is correct
25 Correct 90 ms 2936 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 3212 ms 1280 KB Output is correct
28 Execution timed out 20060 ms 20752 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 1256 KB Output is correct
2 Correct 627 ms 1152 KB Output is correct
3 Correct 651 ms 1272 KB Output is correct
4 Correct 647 ms 1272 KB Output is correct
5 Correct 632 ms 1152 KB Output is correct
6 Correct 23 ms 16120 KB Output is correct
7 Correct 22 ms 16128 KB Output is correct
8 Correct 24 ms 16128 KB Output is correct
9 Correct 70 ms 17400 KB Output is correct
10 Correct 7 ms 8192 KB Output is correct
11 Correct 7 ms 8192 KB Output is correct
12 Correct 97 ms 11000 KB Output is correct
13 Correct 7 ms 8192 KB Output is correct
14 Correct 7 ms 8192 KB Output is correct
15 Correct 2759 ms 26872 KB Output is correct
16 Execution timed out 20015 ms 25408 KB Time limit exceeded
17 Halted 0 ms 0 KB -