oj.uz

Submission #359453

# Submission time Handle Problem Language Result Execution time Memory
359453 2021-01-27T03:06:48 Z tengiz05 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26088 KB 
#include "wombats.h"
#ifndef EVAL
#include "grader.c"
#endif
#include <bits/stdc++.h>
using namespace std;
int n, m;
int h[5000][200], v[5000][200];
int dp[200][200], old[200][200];
void recalc(){
	for(int start = 0; start < m; start++){
		int carry = 0;
		for(int i=start;i<m;i++){
			dp[start][i] = carry;
			carry += h[0][i];
		}carry = 0;
		for(int i=start-1;i>=0;i--){
			carry += h[0][i];
			dp[start][i] = carry;
		}
		for(int row=1;row<n;row++){
			swap(dp[start],old[start]);
			for(int i=0;i<m;i++){
				dp[start][i] = old[start][i] + v[row-1][i];
			}
			for(int i=1;i<m;i++){
				dp[start][i] = min(dp[start][i], dp[start][i-1] + h[row][i-1]);
			}
			for(int i=m-2;i>=0;i--){
				dp[start][i] = min(dp[start][i], dp[start][i+1] + h[row][i]);
			}
		}
	}
	//~ cout << "______________________________\n";
	//~ cout << "what my dp looks like\n";
	//~ for(int i=0;i<m;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout << dp[i][j] << ' ';
		//~ }cout << '\n';
	//~ }cout << "______________________________\n\n";
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
	n = R, m = C;
	for(int i=0;i<5000;i++){
		for(int j=0;j<200;j++){
			h[i][j] = H[i][j];
			v[i][j] = V[i][j];
		}
	}recalc();
}

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

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

int escape(int V1, int V2){
	return dp[V1][V2];
}
/*


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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 12140 KB Output is correct
2 Correct 541 ms 12140 KB Output is correct
3 Correct 611 ms 14956 KB Output is correct
4 Correct 531 ms 12268 KB Output is correct
5 Correct 549 ms 12268 KB Output is correct
6 Correct 9 ms 8300 KB Output is correct
7 Correct 7 ms 8172 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 7 ms 8172 KB Output is correct
3 Correct 7 ms 8172 KB Output is correct
4 Correct 7 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 7 ms 8172 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct
9 Correct 7 ms 8172 KB Output is correct
10 Correct 7 ms 8172 KB Output is correct
11 Correct 86 ms 9196 KB Output is correct
12 Correct 7 ms 8172 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 8548 KB Output is correct
2 Correct 1087 ms 8612 KB Output is correct
3 Correct 1120 ms 8556 KB Output is correct
4 Correct 1126 ms 8632 KB Output is correct
5 Correct 1090 ms 8556 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 7 ms 8172 KB Output is correct
8 Correct 7 ms 8172 KB Output is correct
9 Correct 5539 ms 8684 KB Output is correct
10 Correct 7 ms 8172 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1106 ms 16108 KB Output is correct
2 Correct 1103 ms 16108 KB Output is correct
3 Correct 1104 ms 16108 KB Output is correct
4 Correct 1149 ms 17496 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 8684 KB Output is correct
2 Correct 1085 ms 8556 KB Output is correct
3 Correct 1121 ms 8816 KB Output is correct
4 Correct 1136 ms 8632 KB Output is correct
5 Correct 1094 ms 8684 KB Output is correct
6 Correct 1101 ms 16108 KB Output is correct
7 Correct 1109 ms 16224 KB Output is correct
8 Correct 1117 ms 16112 KB Output is correct
9 Correct 1153 ms 17388 KB Output is correct
10 Correct 535 ms 12268 KB Output is correct
11 Correct 534 ms 12140 KB Output is correct
12 Correct 622 ms 14936 KB Output is correct
13 Correct 536 ms 12140 KB Output is correct
14 Correct 534 ms 12268 KB Output is correct
15 Correct 7 ms 8172 KB Output is correct
16 Correct 7 ms 8172 KB Output is correct
17 Correct 7 ms 8172 KB Output is correct
18 Correct 9 ms 8300 KB Output is correct
19 Correct 7 ms 8300 KB Output is correct
20 Correct 7 ms 8300 KB Output is correct
21 Correct 7 ms 8300 KB Output is correct
22 Correct 7 ms 8300 KB Output is correct
23 Correct 7 ms 8300 KB Output is correct
24 Correct 7 ms 8300 KB Output is correct
25 Correct 86 ms 10604 KB Output is correct
26 Correct 7 ms 8300 KB Output is correct
27 Correct 5532 ms 8688 KB Output is correct
28 Execution timed out 20072 ms 19920 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1146 ms 8552 KB Output is correct
2 Correct 1123 ms 8612 KB Output is correct
3 Correct 1152 ms 8632 KB Output is correct
4 Correct 1154 ms 8556 KB Output is correct
5 Correct 1126 ms 8624 KB Output is correct
6 Correct 1210 ms 16108 KB Output is correct
7 Correct 1113 ms 16108 KB Output is correct
8 Correct 1117 ms 16108 KB Output is correct
9 Correct 1233 ms 17516 KB Output is correct
10 Correct 528 ms 12140 KB Output is correct
11 Correct 525 ms 12140 KB Output is correct
12 Correct 606 ms 14956 KB Output is correct
13 Correct 534 ms 12140 KB Output is correct
14 Correct 588 ms 12140 KB Output is correct
15 Correct 10213 ms 26088 KB Output is correct
16 Execution timed out 20069 ms 24348 KB Time limit exceeded
17 Halted 0 ms 0 KB -