oj.uz

답안 #134863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134863 2019-07-23T10:37:03 Z mirbek01 웜뱃 (IOI13_wombats) C++11
55 / 100
 20000 ms 29932 KB 
#include "wombats.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;
const int M = 202;

int v[N][M], h[N][M], dp[N][M], ans[M][M], r, c;

void build(){
	for(int x = 0; x < c; x ++){
		for(int i = 0; i < r; i ++)
			for(int j = 0; j < c; j ++)
				dp[i][j] = 2e9;
		set < pair <int, pair <int, int> > > st;
		dp[0][x] = 0;
		st.insert({0, {0, x}});
		while(!st.empty()){
			pair <int, int> y = st.begin()->second;
			st.erase(st.begin());
			if(y.second + 1 < c && dp[y.first][y.second + 1] > dp[y.first][y.second] + h[y.first][y.second]){
				st.erase( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );
				dp[y.first][y.second + 1] = dp[y.first][y.second] + h[y.first][y.second];
				st.insert( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );				 
			}
			if(y.second - 1 >= 0 && dp[y.first][y.second - 1] > dp[y.first][y.second] + h[y.first][y.second - 1]){
				st.erase( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );
				dp[y.first][y.second - 1] = dp[y.first][y.second] + h[y.first][y.second - 1];
				st.insert( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );				 
			}
			if(y.first + 1 < r && dp[y.first + 1][y.second] > dp[y.first][y.second] + v[y.first][y.second]){
				st.erase( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );
				dp[y.first + 1][y.second] = dp[y.first][y.second] + v[y.first][y.second];
				st.insert( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );				 
			}			
		}
		for(int y = 0; y < c; y ++)
			ans[x][y] = dp[r - 1][y];
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	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];
	r = R, c = C;
	if(c <= 2)
		build();
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	if(c <= 2)
		build();
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	if(c <= 2)
		build();
}

int escape(int x, int y) {
	if(c > 2){
		for(int i = 0; i < r; i ++)
			for(int j = 0; j < c; j ++)
				dp[i][j] = 2e9;
		set < pair <int, pair <int, int> > > st;
		dp[0][x] = 0;
		st.insert({0, {0, x}});
		while(!st.empty()){
			pair <int, int> y = st.begin()->second;
			st.erase(st.begin());
			if(y.second + 1 < c && dp[y.first][y.second + 1] > dp[y.first][y.second] + h[y.first][y.second]){
				st.erase( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );
				dp[y.first][y.second + 1] = dp[y.first][y.second] + h[y.first][y.second];
				st.insert( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );				 
			}
			if(y.second - 1 >= 0 && dp[y.first][y.second - 1] > dp[y.first][y.second] + h[y.first][y.second - 1]){
				st.erase( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );
				dp[y.first][y.second - 1] = dp[y.first][y.second] + h[y.first][y.second - 1];
				st.insert( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );				 
			}
			if(y.first + 1 < r && dp[y.first + 1][y.second] > dp[y.first][y.second] + v[y.first][y.second]){
				st.erase( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );
				dp[y.first + 1][y.second] = dp[y.first][y.second] + v[y.first][y.second];
				st.insert( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );				 
			}			
		}
		return dp[r - 1][y];
	} else{
		return ans[x][y];
	}
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 12152 KB Output is correct
2 Correct 198 ms 12152 KB Output is correct
3 Correct 271 ms 13816 KB Output is correct
4 Correct 199 ms 12280 KB Output is correct
5 Correct 195 ms 12152 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 37 ms 504 KB Output is correct
5 Correct 20 ms 504 KB Output is correct
6 Correct 20 ms 504 KB Output is correct
7 Correct 32 ms 424 KB Output is correct
8 Correct 33 ms 376 KB Output is correct
9 Correct 36 ms 376 KB Output is correct
10 Correct 33 ms 504 KB Output is correct
11 Correct 17339 ms 1716 KB Output is correct
12 Correct 43 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 888 KB Output is correct
2 Correct 344 ms 836 KB Output is correct
3 Correct 279 ms 892 KB Output is correct
4 Correct 278 ms 888 KB Output is correct
5 Correct 277 ms 888 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 299 ms 804 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1020 ms 20100 KB Output is correct
2 Correct 1006 ms 20216 KB Output is correct
3 Correct 1029 ms 20216 KB Output is correct
4 Correct 1123 ms 20864 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 840 KB Output is correct
2 Correct 349 ms 800 KB Output is correct
3 Correct 278 ms 760 KB Output is correct
4 Correct 286 ms 964 KB Output is correct
5 Correct 277 ms 760 KB Output is correct
6 Correct 1002 ms 20088 KB Output is correct
7 Correct 1026 ms 20060 KB Output is correct
8 Correct 1022 ms 20216 KB Output is correct
9 Correct 1051 ms 21332 KB Output is correct
10 Correct 195 ms 12280 KB Output is correct
11 Correct 194 ms 12152 KB Output is correct
12 Correct 266 ms 14968 KB Output is correct
13 Correct 199 ms 12284 KB Output is correct
14 Correct 194 ms 12260 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 37 ms 504 KB Output is correct
19 Correct 22 ms 508 KB Output is correct
20 Correct 21 ms 504 KB Output is correct
21 Correct 32 ms 512 KB Output is correct
22 Correct 31 ms 376 KB Output is correct
23 Correct 36 ms 520 KB Output is correct
24 Correct 32 ms 376 KB Output is correct
25 Correct 17361 ms 3076 KB Output is correct
26 Correct 43 ms 376 KB Output is correct
27 Correct 300 ms 888 KB Output is correct
28 Execution timed out 20055 ms 23544 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 760 KB Output is correct
2 Correct 348 ms 808 KB Output is correct
3 Correct 279 ms 888 KB Output is correct
4 Correct 279 ms 760 KB Output is correct
5 Correct 277 ms 888 KB Output is correct
6 Correct 1002 ms 20088 KB Output is correct
7 Correct 1014 ms 20192 KB Output is correct
8 Correct 1020 ms 20088 KB Output is correct
9 Correct 1057 ms 21240 KB Output is correct
10 Correct 195 ms 12152 KB Output is correct
11 Correct 199 ms 12252 KB Output is correct
12 Correct 274 ms 14912 KB Output is correct
13 Correct 194 ms 12280 KB Output is correct
14 Correct 196 ms 12152 KB Output is correct
15 Correct 1219 ms 29932 KB Output is correct
16 Execution timed out 20046 ms 27900 KB Time limit exceeded
17 Halted 0 ms 0 KB -