oj.uz

Submission #134859

# Submission time Handle Problem Language Result Execution time Memory
134859 2019-07-23T10:27:10 Z mirbek01 Wombats (IOI13_wombats) C++11
39 / 100
 20000 ms 21568 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) {
	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

# Verdict Execution time Memory Grader output
1 Correct 212 ms 12280 KB Output is correct
2 Correct 215 ms 12180 KB Output is correct
3 Correct 441 ms 15000 KB Output is correct
4 Correct 225 ms 12152 KB Output is correct
5 Correct 216 ms 12280 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

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 380 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 4 ms 476 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 86 ms 2872 KB Output is correct
12 Correct 5 ms 504 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20077 ms 988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 20184 KB Output is correct
2 Correct 1054 ms 20316 KB Output is correct
3 Correct 1026 ms 20176 KB Output is correct
4 Correct 1063 ms 21568 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20017 ms 1032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20022 ms 1160 KB Time limit exceeded
2 Halted 0 ms 0 KB -