Submission #411658

#	Time	Username	Problem	Language	Result	Execution time	Memory
411658		albertolg101	Wombats (IOI13_wombats)	C++17	28 / 100	20066 ms	32976 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;
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];
		}
	}
}

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

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

int escape(int V1, int V2)
{
	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];
		}
	}

	return dp[0][V1];
}

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