oj.uz

Submission #868678

# Submission time Handle Problem Language Result Execution time Memory
868678 2023-11-01T12:09:06 Z faremy Soccer Stadium (IOI23_soccer) C++17
6 / 100
 328 ms 70936 KB 
#include "soccer.h"

#include <stack>


struct Rectangle
{
	Rectangle(int w, int h) : width(w), height(h) {}
	int width, height;
};

const int MAXN = 2000;

int longest_above[MAXN][MAXN];
int longest_below[MAXN][MAXN];


void fill_longest(int N, std::vector<std::vector<int>> &F)
{
	for (int iCol = 0; iCol < N; iCol++)
		longest_above[0][iCol] = 0;
	for (int iRow = 1; iRow < N; iRow++)
		for (int iCol = 0; iCol < N; iCol++)
			longest_above[iRow][iCol] = (F[iRow - 1][iCol] ? 0 : longest_above[iRow - 1][iCol] + 1);

	for (int iCol = 0; iCol < N; iCol++)
		longest_below[N - 1][iCol] = 0;
	for (int iRow = N - 2; iRow > -1; iRow--)
		for (int iCol = 0; iCol < N; iCol++)
			longest_below[iRow][iCol] = (F[iRow + 1][iCol] ? 0 : longest_below[iRow + 1][iCol] + 1);
}

void profile_push(std::stack<Rectangle> &profile, int &profile_size, int h)
{
	int w = 1;
	while (profile.top().height > h)
	{
		w += profile.top().width;
		profile_size -= profile.top().width * profile.top().height;
		profile.pop();
	}

	profile_size += w * h;
	profile.emplace(w, h);
}

void profile_clear(std::stack<Rectangle> &profile)
{
	while (!profile.empty())
		profile.pop();
}

int best_stadium(int row, int begin_col, int end_col)
{
	int stadium_width = end_col - begin_col;
	std::vector<int> profile(stadium_width, 0);

	std::stack<Rectangle> above_profile;
	above_profile.emplace(0, 0);
	std::stack<Rectangle> below_profile;
	below_profile.emplace(0, 0);
	int profile_size = 0;

	for (int iCol = begin_col; iCol < end_col; iCol++)
	{
		profile_push(above_profile, profile_size, longest_above[row][iCol]);
		profile_push(below_profile, profile_size, longest_below[row][iCol]);
		profile[iCol - begin_col] += profile_size;
	}

	profile_clear(above_profile);
	above_profile.emplace(0, 0);
	profile_clear(below_profile);
	below_profile.emplace(0, 0);
	profile_size = 0;

	for (int iCol = end_col - 1; iCol >= begin_col; iCol--)
	{
		profile_push(above_profile, profile_size, longest_above[row][iCol]);
		profile_push(below_profile, profile_size, longest_below[row][iCol]);
		profile[iCol - begin_col] += profile_size - above_profile.top().height - below_profile.top().height;
	}

	int best_profile = 0;
	for (int iCol = 0; iCol < stadium_width; iCol++)
		best_profile = std::max(best_profile, profile[iCol]);
	return (best_profile + stadium_width);
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	fill_longest(N, F);

	int max_stadium = 0;
	for (int iRow = 0; iRow < N; iRow++)
		for (int begin_col = 0, end_col; begin_col < N; begin_col = end_col + 1)
		{
			end_col = begin_col;
			while (end_col < N && F[iRow][end_col] == 0)
				end_col++;
			max_stadium = std::max(max_stadium, best_stadium(iRow, begin_col, end_col));
		}

    return max_stadium;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 1 ms 2796 KB ok
8 Correct 22 ms 13924 KB ok
9 Correct 328 ms 70936 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Incorrect 0 ms 2396 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok
2 Correct 1 ms 2392 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Incorrect 0 ms 2396 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok
2 Correct 1 ms 2392 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 0 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Incorrect 0 ms 2396 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok
2 Correct 1 ms 2392 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 0 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Incorrect 0 ms 2396 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok
2 Correct 1 ms 2392 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 2796 KB ok
9 Correct 22 ms 13924 KB ok
10 Correct 328 ms 70936 KB ok
11 Correct 0 ms 2396 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 0 ms 2396 KB ok
14 Correct 0 ms 2396 KB ok
15 Incorrect 0 ms 2396 KB wrong
16 Halted 0 ms 0 KB -