oj.uz

Submission #414543

# Submission time Handle Problem Language Result Execution time Memory
414543 2021-05-30T15:47:36 Z faresbasbs Wombats (IOI13_wombats) C++14
55 / 100
 18784 ms 262148 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
unordered_map<int,unordered_map<int,unordered_map<int,unordered_map<int,int>>>> dp;
int n,m,h[5000][200],v[5000][200];

int ans(int r , int c , int en , int tag){
	if(r == n-1 && c == en){
		return 0;
	}
	if(dp.find(r) != dp.end() && dp[r].find(c) != dp[r].end() && dp[r][c].find(en) != dp[r][c].end() && dp[r][c][en].find(tag) != dp[r][c][en].end()){
		return dp[r][c][en][tag];
	}
	int ret = 1000000000;
	if(!tag){
		if(c){
			ret = min(ret,h[r][c-1]+ans(r,c-1,en,tag));
		}
	}else{
		if(c+1 < m){
			ret = min(ret,h[r][c]+ans(r,c+1,en,tag));
		}
	}
	if(r+1 < n){
		ret = min(ret,v[r][c]+min(ans(r+1,c,en,0),ans(r+1,c,en,1)));
	}
	return dp[r][c][en][tag] = ret;
}

void re(){
	dp.clear();
}

void init(int R , int C , int H[5000][200] , int V[5000][200]){
	n = R , m = C;
	for(int i = 0 ; i < n ; i += 1){
		for(int j = 0 ; j < m ; j += 1){
			h[i][j] = H[i][j] , v[i][j] = V[i][j];
		}
	}
	re();
}

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

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

int escape(int V1 , int V2){
	return min(ans(0,V1,V2,0),ans(0,V1,V2,1));
}

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 3415 ms 15588 KB Output is correct
2 Correct 3572 ms 15572 KB Output is correct
3 Correct 3809 ms 17260 KB Output is correct
4 Correct 3481 ms 15572 KB Output is correct
5 Correct 3485 ms 15576 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 12 ms 2440 KB Output is correct
5 Correct 13 ms 2476 KB Output is correct
6 Correct 12 ms 2508 KB Output is correct
7 Correct 14 ms 2508 KB Output is correct
8 Correct 11 ms 2124 KB Output is correct
9 Correct 11 ms 2380 KB Output is correct
10 Correct 13 ms 2252 KB Output is correct
11 Correct 159 ms 3508 KB Output is correct
12 Correct 12 ms 2508 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 142592 KB Output is correct
2 Correct 1450 ms 12444 KB Output is correct
3 Correct 1430 ms 15144 KB Output is correct
4 Correct 1544 ms 15136 KB Output is correct
5 Correct 1521 ms 14996 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 744 ms 7636 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17892 ms 24184 KB Output is correct
2 Correct 18784 ms 24232 KB Output is correct
3 Correct 18473 ms 24256 KB Output is correct
4 Correct 18283 ms 25592 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 142480 KB Output is correct
2 Correct 1433 ms 12520 KB Output is correct
3 Correct 1433 ms 15032 KB Output is correct
4 Correct 1469 ms 15140 KB Output is correct
5 Correct 1418 ms 14996 KB Output is correct
6 Correct 17919 ms 24188 KB Output is correct
7 Correct 17889 ms 24240 KB Output is correct
8 Correct 17870 ms 24252 KB Output is correct
9 Correct 17606 ms 25612 KB Output is correct
10 Correct 3253 ms 15684 KB Output is correct
11 Correct 3303 ms 15684 KB Output is correct
12 Correct 3418 ms 18040 KB Output is correct
13 Correct 3262 ms 15564 KB Output is correct
14 Correct 3290 ms 15612 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 12 ms 2460 KB Output is correct
19 Correct 12 ms 2472 KB Output is correct
20 Correct 12 ms 2520 KB Output is correct
21 Correct 12 ms 2420 KB Output is correct
22 Correct 10 ms 2160 KB Output is correct
23 Correct 11 ms 2380 KB Output is correct
24 Correct 11 ms 2252 KB Output is correct
25 Correct 156 ms 4468 KB Output is correct
26 Correct 12 ms 2508 KB Output is correct
27 Correct 696 ms 7840 KB Output is correct
28 Runtime error 929 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 142540 KB Output is correct
2 Correct 1391 ms 12444 KB Output is correct
3 Correct 1404 ms 15252 KB Output is correct
4 Correct 1560 ms 15396 KB Output is correct
5 Correct 1417 ms 15024 KB Output is correct
6 Correct 17945 ms 24260 KB Output is correct
7 Correct 16828 ms 24236 KB Output is correct
8 Correct 17482 ms 24252 KB Output is correct
9 Correct 17235 ms 25608 KB Output is correct
10 Correct 3231 ms 15596 KB Output is correct
11 Correct 3287 ms 15616 KB Output is correct
12 Correct 3448 ms 17860 KB Output is correct
13 Correct 3265 ms 15684 KB Output is correct
14 Correct 3259 ms 15608 KB Output is correct
15 Runtime error 1036 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -