oj.uz

Submission #530600

# Submission time Handle Problem Language Result Execution time Memory
530600 2022-02-26T02:19:12 Z jjang36524 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 34672 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 };
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

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 309 ms 29020 KB Output is correct
2 Correct 304 ms 29016 KB Output is correct
3 Correct 373 ms 30680 KB Output is correct
4 Correct 309 ms 29016 KB Output is correct
5 Correct 340 ms 29020 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 KB Output is correct
11 Correct 62 ms 1788 KB Output is correct
12 Correct 1 ms 844 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 1464 KB Output is correct
2 Correct 308 ms 1480 KB Output is correct
3 Correct 483 ms 1472 KB Output is correct
4 Correct 486 ms 1460 KB Output is correct
5 Correct 468 ms 1476 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1605 ms 1460 KB Output is correct
10 Correct 1 ms 844 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 32924 KB Output is correct
2 Correct 317 ms 32908 KB Output is correct
3 Correct 311 ms 32920 KB Output is correct
4 Correct 379 ms 33720 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 1464 KB Output is correct
2 Correct 308 ms 1356 KB Output is correct
3 Correct 487 ms 1456 KB Output is correct
4 Correct 490 ms 1356 KB Output is correct
5 Correct 515 ms 1480 KB Output is correct
6 Correct 310 ms 32844 KB Output is correct
7 Correct 308 ms 32964 KB Output is correct
8 Correct 323 ms 32920 KB Output is correct
9 Correct 358 ms 33716 KB Output is correct
10 Correct 334 ms 29016 KB Output is correct
11 Correct 308 ms 29004 KB Output is correct
12 Correct 374 ms 30552 KB Output is correct
13 Correct 306 ms 28960 KB Output is correct
14 Correct 338 ms 29024 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 0 ms 716 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 2 ms 848 KB Output is correct
19 Correct 1 ms 844 KB Output is correct
20 Correct 1 ms 844 KB Output is correct
21 Correct 1 ms 844 KB Output is correct
22 Correct 1 ms 844 KB Output is correct
23 Correct 1 ms 844 KB Output is correct
24 Correct 1 ms 844 KB Output is correct
25 Correct 64 ms 1872 KB Output is correct
26 Correct 1 ms 844 KB Output is correct
27 Correct 1588 ms 1464 KB Output is correct
28 Correct 4888 ms 33348 KB Output is correct
29 Correct 5608 ms 27736 KB Output is correct
30 Correct 5895 ms 27604 KB Output is correct
31 Correct 4792 ms 34672 KB Output is correct
32 Correct 1 ms 844 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 1484 KB Output is correct
2 Correct 329 ms 1484 KB Output is correct
3 Correct 470 ms 1564 KB Output is correct
4 Correct 470 ms 1356 KB Output is correct
5 Correct 474 ms 1476 KB Output is correct
6 Correct 305 ms 32972 KB Output is correct
7 Correct 318 ms 32916 KB Output is correct
8 Correct 311 ms 32920 KB Output is correct
9 Correct 340 ms 33992 KB Output is correct
10 Correct 309 ms 28928 KB Output is correct
11 Correct 301 ms 28952 KB Output is correct
12 Correct 366 ms 30528 KB Output is correct
13 Correct 313 ms 29012 KB Output is correct
14 Correct 301 ms 29000 KB Output is correct
15 Correct 1497 ms 33240 KB Output is correct
16 Execution timed out 20040 ms 34392 KB Time limit exceeded
17 Halted 0 ms 0 KB -