Submission #1037444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037444		aaaaaarroz	Soccer Stadium (IOI23_soccer)	C++17	34.50 / 100	4575 ms	6892 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int n, vector<vector<int>> f) {
	vector<vector<int>> up(n, vector<int>(n)), down(n, vector<int>(n)), left(n, vector<int>(n)), right(n, vector<int>(n));
	for(int x=0;x<n;x++) {
		up[0][x] = 1 - f[0][x];
		for (int y = 1; y < n; y++) {
			if (f[y][x])
				up[y][x] = 0;
			else
				up[y][x] = up[y - 1][x] + 1;
	
		}
		down[n - 1][x] = 1 - f[n - 1][x];
		for (int y = n - 2; y >= 0; y--) {
			if (f[y][x])
				down[y][x] = 0;
			else
				down[y][x] = down[y + 1][x] + 1;
		}
	}
	for(int y=0;y<n;y++) {
		left[y][0] = 1 - f[y][0];
		for (int x = 1; x < n; x++) {
			if (f[y][x])
				left[y][x] = 0;
			else
				left[y][x] = left[y][x - 1] + 1;
	
		}
		right[y][n - 1] = 1 - f[y][n - 1];
		for (int x = n - 2; x >= 0; x--) {
			if (f[y][x])
				right[y][x] = 0;
			else
				right[y][x] = right[y][x + 1] + 1;
		}
	}
	int result = 0;
	for(int y=0;y<n;y++) {
		for(int x=0;x<n;x++) {
			if (f[y][x]) {
				continue;
			}
	
			int count1 = 0;
			int l = 0, r = INT_MAX;
			vector<pair<int,int>> intervals;
			for (int y2 = y; y2 < y + down[y][x]; y2++) {
				l = max(l, x - left[y2][x] + 1);
				r = min(r, x + right[y2][x] - 1);
	
				intervals.push_back({ l, r });
				count1 += r - l + 1;
			}
			l = x - left[y][x] + 1;
			r = x + right[y][x] - 1;
			for (int y2 = y - 1; y2 > y - up[y][x]; y2--) {
				l = max(l, x - left[y2][x] + 1);
				r = min(r, x + right[y2][x] - 1);
	
				for (auto [li, ri] : intervals) {
					if (r < ri)
						l = max(l, li);
	
					if (l > li)
						r = min(r, ri);
				}
	
				if (r < l)
					break;
	
				count1 += r - l + 1;
			}
			int count = count1;
			result = max(result, count);
		}
	}
	return result;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30