Submission #530600

#	Time	Username	Problem	Language	Result	Execution time	Memory
530600		jjang36524	Wombats (IOI13_wombats)	C++14	76 / 100	20040 ms	34672 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
int finans[205][205];
int sqrtans[100][205][205];
int sqrts[100], sqrte[100];
int h[5005][205], v[5005][205];
int n, m,di,ss;
int tempans[205][205] = { 0 };
int opt[205][205] = { 0 };
int curco[205][205] = { 0 };
void sqrtcal(int n)
{
	
	memset(sqrtans[n], 10, sizeof(sqrtans[n]));
	int i;
	for (i = 0; i < m; i++)
		sqrtans[n][i][i] = 0;
	for (i = sqrts[n]; i <= sqrte[n]; i++)
	{
		memset(tempans, 10, sizeof(tempans));
		int j,k;
		
		int currdi = 0;
		for (j = 0; j < m; j++)
		{
			int curdi = currdi;
			for (k = 0; k < m; k++)
			{
				curco[j][k] = v[i][k] + curdi;
				if (k < j)
				{
					curdi -= h[i][k];
				}
				else
				{
					curdi += h[i][k];
				}
			}
			currdi += h[i][j];
		}
		for (j = 0; j < m; j++)
		{
			for (k = m - 1; k >= 0; k--)
			{
				int l;
				for (l = (j ? opt[j - 1][k] : 0); l <= (k < m - 1 ? opt[j][k + 1] : m - 1); l++)
				{
					if (tempans[j][k] > sqrtans[n][j][l] + curco[l][k])
					{
						tempans[j][k] = sqrtans[n][j][l] + curco[l][k];
						opt[j][k] = l;
					}
				}
			}
		}
		for (j = 0; j < m; j++)
		{
			for (k = 0; k < m; k++)
			{
				sqrtans[n][j][k] = tempans[j][k];
			}
		}
	}
}
void fincal()
{
	memset(finans, 10, sizeof(finans));
	int i;
	for (i = 0; i < m; i++)
		finans[i][i] = 0;
	for (i =0; i <ss; i++)
	{
		memset(tempans, 10, sizeof(tempans));
		int j, k;

		for (j = 0; j < m; j++)
		{
			for (k = m - 1; k >= 0; k--)
			{
				int l;
				for (l = (j ? opt[j - 1][k] : 0); l <= (k < m - 1 ? opt[j][k + 1] : m - 1); l++)
				{
					if (tempans[j][k] > finans[j][l] + sqrtans[i][l][k])
					{
						tempans[j][k] = finans[j][l] + sqrtans[i][l][k];
						opt[j][k] = l;
					}
				}
			}
		}
		for (j = 0; j < m; j++)
		{
			for (k = 0; k < m; k++)
			{
				finans[j][k] = tempans[j][k];
			}
		}
	}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) 
{
	n = R;
	m = C;
	di = 50;
	int i;
	for (i = 0; i * di < n; i++)
	{
		sqrts[i] = i * di;
		sqrte[i] = min(i * di + di - 1, n - 1);
	}
	ss = i;
	for (i = 0; i < n; i++)
	{
		int j;
		for (j = 0; j < m; j++)
		{
			h[i][j] = H[i][j];
			v[i][j] = V[i][j];
		}
	}
	for (i = 0; i < ss; i++)
	{
		sqrtcal(i);
	}
	fincal();
}

void changeH(int P, int Q, int W) 
{
	h[P][Q] = W;
	sqrtcal(P / di);
	fincal();
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	sqrtcal(P / di);
	fincal();
}

int escape(int V1, int V2) {
	return finans[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: 21 / 21
• Subtask 6: 0 / 24