oj.uz

Submission #530599

# Submission time Handle Problem Language Result Execution time Memory
530599 2022-02-26T02:18:12 Z jjang36524 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 34820 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;
int tempans[205][205] = { 0 };
int opt[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 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()
{
	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

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 519 ms 29236 KB Output is correct
2 Correct 564 ms 29340 KB Output is correct
3 Correct 615 ms 30868 KB Output is correct
4 Correct 529 ms 29340 KB Output is correct
5 Correct 532 ms 29336 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Correct 1 ms 1228 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 2 ms 1228 KB Output is correct
11 Correct 64 ms 2148 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 1700 KB Output is correct
2 Correct 381 ms 1700 KB Output is correct
3 Correct 555 ms 1720 KB Output is correct
4 Correct 596 ms 1612 KB Output is correct
5 Correct 573 ms 1700 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1932 ms 1692 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 33244 KB Output is correct
2 Correct 532 ms 33240 KB Output is correct
3 Correct 537 ms 33240 KB Output is correct
4 Correct 661 ms 33984 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 1696 KB Output is correct
2 Correct 373 ms 1612 KB Output is correct
3 Correct 584 ms 1684 KB Output is correct
4 Correct 581 ms 1696 KB Output is correct
5 Correct 552 ms 1700 KB Output is correct
6 Correct 611 ms 33248 KB Output is correct
7 Correct 576 ms 33244 KB Output is correct
8 Correct 544 ms 33244 KB Output is correct
9 Correct 587 ms 33964 KB Output is correct
10 Correct 583 ms 29336 KB Output is correct
11 Correct 675 ms 29336 KB Output is correct
12 Correct 622 ms 30868 KB Output is correct
13 Correct 643 ms 29340 KB Output is correct
14 Correct 536 ms 29336 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 1 ms 1100 KB Output is correct
18 Correct 1 ms 1228 KB Output is correct
19 Correct 1 ms 1228 KB Output is correct
20 Correct 1 ms 1228 KB Output is correct
21 Correct 1 ms 1228 KB Output is correct
22 Correct 1 ms 1228 KB Output is correct
23 Correct 1 ms 1228 KB Output is correct
24 Correct 1 ms 1228 KB Output is correct
25 Correct 64 ms 2108 KB Output is correct
26 Correct 1 ms 1228 KB Output is correct
27 Correct 1877 ms 1700 KB Output is correct
28 Correct 4965 ms 33724 KB Output is correct
29 Correct 6065 ms 27848 KB Output is correct
30 Correct 6215 ms 27860 KB Output is correct
31 Correct 4747 ms 34820 KB Output is correct
32 Correct 1 ms 1100 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 1680 KB Output is correct
2 Correct 362 ms 1692 KB Output is correct
3 Correct 561 ms 1692 KB Output is correct
4 Correct 553 ms 1692 KB Output is correct
5 Correct 539 ms 1696 KB Output is correct
6 Correct 542 ms 33328 KB Output is correct
7 Correct 527 ms 33248 KB Output is correct
8 Correct 534 ms 33244 KB Output is correct
9 Correct 561 ms 33992 KB Output is correct
10 Correct 521 ms 29332 KB Output is correct
11 Correct 535 ms 29336 KB Output is correct
12 Correct 609 ms 30900 KB Output is correct
13 Correct 567 ms 29340 KB Output is correct
14 Correct 552 ms 29336 KB Output is correct
15 Correct 1714 ms 33308 KB Output is correct
16 Execution timed out 20040 ms 34564 KB Time limit exceeded
17 Halted 0 ms 0 KB -