oj.uz

Submission #134861

# Submission time Handle Problem Language Result Execution time Memory
134861 2019-07-23T10:32:06 Z mirbek01 Wombats (IOI13_wombats) C++11
28 / 100
 20000 ms 20920 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;
//	build();
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	//build();
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	//build();
}

int escape(int x, int y) {
		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];
}
/***
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1
 ***/

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 12284 KB Output is correct
2 Correct 202 ms 12280 KB Output is correct
3 Execution timed out 20005 ms 12968 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 39 ms 376 KB Output is correct
5 Correct 22 ms 636 KB Output is correct
6 Correct 21 ms 504 KB Output is correct
7 Correct 32 ms 476 KB Output is correct
8 Correct 32 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 17538 ms 1820 KB Output is correct
12 Correct 43 ms 376 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 800 KB Output is correct
2 Correct 352 ms 764 KB Output is correct
3 Correct 293 ms 888 KB Output is correct
4 Correct 293 ms 888 KB Output is correct
5 Correct 305 ms 1016 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 380 KB Output is correct
9 Correct 299 ms 1008 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1029 ms 20064 KB Output is correct
2 Correct 1008 ms 20096 KB Output is correct
3 Correct 1060 ms 20216 KB Output is correct
4 Execution timed out 20014 ms 20548 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 888 KB Output is correct
2 Correct 346 ms 760 KB Output is correct
3 Correct 280 ms 888 KB Output is correct
4 Correct 282 ms 888 KB Output is correct
5 Correct 282 ms 896 KB Output is correct
6 Correct 1267 ms 20264 KB Output is correct
7 Correct 1000 ms 20240 KB Output is correct
8 Correct 1042 ms 20260 KB Output is correct
9 Execution timed out 20100 ms 20880 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 796 KB Output is correct
2 Correct 346 ms 1004 KB Output is correct
3 Correct 282 ms 1016 KB Output is correct
4 Correct 280 ms 988 KB Output is correct
5 Correct 280 ms 888 KB Output is correct
6 Correct 1057 ms 20216 KB Output is correct
7 Correct 1064 ms 20252 KB Output is correct
8 Correct 1044 ms 20216 KB Output is correct
9 Execution timed out 20055 ms 20920 KB Time limit exceeded
10 Halted 0 ms 0 KB -