oj.uz

Submission #411662

# Submission time Handle Problem Language Result Execution time Memory
411662 2021-05-25T17:12:48 Z albertolg101 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 42520 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

using pii = pair<long long, long long>;

const long long INF = 1e12;
int n, m;
vector<vector<long long>> h(5001, vector<long long> (201)), v = h, dp = h, memo;
bool sol = false;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n = R, m = C;

	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];
		}
	}

	memo = vector<vector<long long>> (m, vector<long long> (m, -1));
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	sol = false;

	memo = vector<vector<long long>> (m, vector<long long> (m, -1));
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	sol = false;

	memo = vector<vector<long long>> (m, vector<long long> (m, -1));
}

int escape(int V1, int V2)
{
	if(memo[V1][V2] == -1)
	{
		for(int i = 0 ; i < m ; i++)
		{
			dp[n-1][i] = INF;
		}
		dp[n-1][V2] = 0;

		for(int i = n - 1 ; i >= 0 ; i--)
		{
			priority_queue<pii, vector<pii>, greater<pii>> q;

			for(int j = 0 ; j < m ; j++)
			{ 
				q.push({dp[i][j], j});
			}

			while(q.size())
			{
				long long j, dist;
				tie(dist, j) = q.top();
				q.pop();

				//if(dp[i][j] < dist)
				//	continue;

				if(j - 1 >= 0 and dp[i][j-1] > dist + h[i][j-1])
				{
					dp[i][j-1] = dist + h[i][j-1];
					q.push({dp[i][j-1], j-1});
				}

				if(j + 1 < m and dp[i][j+1] > dist + h[i][j])
				{
					dp[i][j+1] = dist + h[i][j];
					q.push({dp[i][j+1], j+1});
				}
			}

			for(int j = 0 ; j < m and i != 0; j++)
			{
				dp[i-1][j] = dp[i][j] + v[i-1][j];
			}
		}


		for(int i = 0 ; i < m ; i++)
		{
			memo[i][V2] = dp[0][i];
		}
	}

	return memo[V1][V2];
}

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 122 ms 28236 KB Output is correct
2 Correct 122 ms 28220 KB Output is correct
3 Correct 197 ms 30312 KB Output is correct
4 Correct 118 ms 28292 KB Output is correct
5 Correct 121 ms 28244 KB Output is correct
6 Correct 17 ms 24376 KB Output is correct
7 Correct 18 ms 24440 KB Output is correct
8 Correct 17 ms 24260 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24260 KB Output is correct
2 Correct 17 ms 24284 KB Output is correct
3 Correct 16 ms 24268 KB Output is correct
4 Correct 18 ms 24396 KB Output is correct
5 Correct 18 ms 24364 KB Output is correct
6 Correct 18 ms 24396 KB Output is correct
7 Correct 18 ms 24340 KB Output is correct
8 Correct 18 ms 24340 KB Output is correct
9 Correct 18 ms 24396 KB Output is correct
10 Correct 21 ms 24300 KB Output is correct
11 Correct 97 ms 25352 KB Output is correct
12 Correct 19 ms 24380 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 24652 KB Output is correct
2 Correct 108 ms 24696 KB Output is correct
3 Correct 148 ms 24652 KB Output is correct
4 Correct 142 ms 24688 KB Output is correct
5 Correct 141 ms 24684 KB Output is correct
6 Correct 17 ms 24268 KB Output is correct
7 Correct 17 ms 24380 KB Output is correct
8 Correct 17 ms 24336 KB Output is correct
9 Correct 76 ms 24696 KB Output is correct
10 Correct 18 ms 24424 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 32136 KB Output is correct
2 Correct 628 ms 32176 KB Output is correct
3 Correct 563 ms 32180 KB Output is correct
4 Correct 630 ms 33140 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 24652 KB Output is correct
2 Correct 108 ms 24692 KB Output is correct
3 Correct 145 ms 24704 KB Output is correct
4 Correct 142 ms 24684 KB Output is correct
5 Correct 144 ms 24692 KB Output is correct
6 Correct 572 ms 32180 KB Output is correct
7 Correct 624 ms 32172 KB Output is correct
8 Correct 562 ms 32196 KB Output is correct
9 Correct 610 ms 33092 KB Output is correct
10 Correct 121 ms 28296 KB Output is correct
11 Correct 122 ms 28304 KB Output is correct
12 Correct 201 ms 31064 KB Output is correct
13 Correct 125 ms 28352 KB Output is correct
14 Correct 119 ms 28236 KB Output is correct
15 Correct 18 ms 24260 KB Output is correct
16 Correct 17 ms 24256 KB Output is correct
17 Correct 19 ms 24376 KB Output is correct
18 Correct 19 ms 24380 KB Output is correct
19 Correct 18 ms 24380 KB Output is correct
20 Correct 18 ms 24304 KB Output is correct
21 Correct 19 ms 24388 KB Output is correct
22 Correct 20 ms 24384 KB Output is correct
23 Correct 18 ms 24396 KB Output is correct
24 Correct 18 ms 24376 KB Output is correct
25 Correct 93 ms 26664 KB Output is correct
26 Correct 18 ms 24376 KB Output is correct
27 Correct 75 ms 24744 KB Output is correct
28 Execution timed out 20045 ms 35908 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 24652 KB Output is correct
2 Correct 110 ms 24692 KB Output is correct
3 Correct 142 ms 24684 KB Output is correct
4 Correct 148 ms 24652 KB Output is correct
5 Correct 140 ms 24688 KB Output is correct
6 Correct 565 ms 32196 KB Output is correct
7 Correct 625 ms 32196 KB Output is correct
8 Correct 561 ms 32180 KB Output is correct
9 Correct 613 ms 33032 KB Output is correct
10 Correct 122 ms 28292 KB Output is correct
11 Correct 122 ms 28296 KB Output is correct
12 Correct 203 ms 31012 KB Output is correct
13 Correct 120 ms 28220 KB Output is correct
14 Correct 120 ms 28216 KB Output is correct
15 Correct 516 ms 42520 KB Output is correct
16 Execution timed out 20048 ms 40684 KB Time limit exceeded
17 Halted 0 ms 0 KB -