Submission #411662

#	Time	Username	Problem	Language	Result	Execution time	Memory
411662		albertolg101	Wombats (IOI13_wombats)	C++17	55 / 100	20048 ms	42520 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24