Submission #868678

#	Time	Username	Problem	Language	Result	Execution time	Memory
868678		faremy	Soccer Stadium (IOI23_soccer)	C++17	6 / 100	328 ms	70936 KiB

soccer

#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
• Subtask 1: 6 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30