oj.uz

Submission #530598

# Submission time Handle Problem Language Result Execution time Memory
530598 2022-02-26T02:13:21 Z jjang36524 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 39220 KB 
#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;
void sqrtcal(int n)
{
	int tempans[205][205] = { 0 };
	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 curco[205][205] = { 0 };
		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];
		}
		int opt[205][205] = { 0 };
		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()
{
	int tempans[205][205] = { 0 };
	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;
		int opt[205][205] = { 0 };
		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 = sqrt(R);
	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

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 694 ms 24756 KB Output is correct
2 Correct 698 ms 24868 KB Output is correct
3 Correct 786 ms 27540 KB Output is correct
4 Correct 720 ms 24772 KB Output is correct
5 Correct 710 ms 24776 KB Output is correct
6 Correct 1 ms 1232 KB Output is correct
7 Correct 1 ms 1232 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1188 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1276 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 2 ms 1848 KB Output is correct
6 Correct 2 ms 1844 KB Output is correct
7 Correct 2 ms 1872 KB Output is correct
8 Correct 1 ms 1872 KB Output is correct
9 Correct 2 ms 1872 KB Output is correct
10 Correct 2 ms 1872 KB Output is correct
11 Correct 65 ms 4152 KB Output is correct
12 Correct 2 ms 1872 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 3172 KB Output is correct
2 Correct 136 ms 3108 KB Output is correct
3 Correct 192 ms 3024 KB Output is correct
4 Correct 191 ms 3016 KB Output is correct
5 Correct 194 ms 3024 KB Output is correct
6 Correct 1 ms 1232 KB Output is correct
7 Correct 1 ms 1232 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct
9 Correct 647 ms 3024 KB Output is correct
10 Correct 1 ms 1488 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 28840 KB Output is correct
2 Correct 703 ms 28600 KB Output is correct
3 Correct 747 ms 28712 KB Output is correct
4 Correct 758 ms 30204 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 3184 KB Output is correct
2 Correct 138 ms 3152 KB Output is correct
3 Correct 195 ms 3016 KB Output is correct
4 Correct 187 ms 2968 KB Output is correct
5 Correct 188 ms 3072 KB Output is correct
6 Correct 706 ms 28752 KB Output is correct
7 Correct 856 ms 28696 KB Output is correct
8 Correct 812 ms 28720 KB Output is correct
9 Correct 743 ms 30024 KB Output is correct
10 Correct 725 ms 24760 KB Output is correct
11 Correct 710 ms 24808 KB Output is correct
12 Correct 767 ms 27544 KB Output is correct
13 Correct 762 ms 24768 KB Output is correct
14 Correct 733 ms 24768 KB Output is correct
15 Correct 1 ms 1232 KB Output is correct
16 Correct 1 ms 1232 KB Output is correct
17 Correct 1 ms 1232 KB Output is correct
18 Correct 2 ms 1872 KB Output is correct
19 Correct 2 ms 1844 KB Output is correct
20 Correct 1 ms 1848 KB Output is correct
21 Correct 2 ms 1872 KB Output is correct
22 Correct 2 ms 1872 KB Output is correct
23 Correct 2 ms 1848 KB Output is correct
24 Correct 2 ms 1872 KB Output is correct
25 Correct 64 ms 4148 KB Output is correct
26 Correct 2 ms 1872 KB Output is correct
27 Correct 655 ms 3032 KB Output is correct
28 Correct 5174 ms 32916 KB Output is correct
29 Correct 5926 ms 28680 KB Output is correct
30 Correct 6204 ms 28408 KB Output is correct
31 Correct 5080 ms 34968 KB Output is correct
32 Correct 1 ms 1488 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 3180 KB Output is correct
2 Correct 138 ms 3176 KB Output is correct
3 Correct 188 ms 2980 KB Output is correct
4 Correct 187 ms 3016 KB Output is correct
5 Correct 190 ms 2924 KB Output is correct
6 Correct 705 ms 28828 KB Output is correct
7 Correct 711 ms 28748 KB Output is correct
8 Correct 931 ms 28720 KB Output is correct
9 Correct 901 ms 30084 KB Output is correct
10 Correct 747 ms 24760 KB Output is correct
11 Correct 892 ms 24776 KB Output is correct
12 Correct 771 ms 27428 KB Output is correct
13 Correct 717 ms 24776 KB Output is correct
14 Correct 762 ms 24856 KB Output is correct
15 Correct 1631 ms 38412 KB Output is correct
16 Execution timed out 20091 ms 39220 KB Time limit exceeded
17 Halted 0 ms 0 KB -