Submission #1064056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064056		DorostWef	Soccer Stadium (IOI23_soccer)	C++17	6 / 100	213 ms	45356 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;
const int N = 2004;
int u[N][N];
int d[N][N];

vector <int> get (vector <int> a) {
	int n = (int)a.size();
	vector <int> b(n);
	for (int i = 0; i < n; i++) {
		int mn = a[i], sum = 0;
		for (int j = i; j >= 0; j--) {
			mn = min(mn, a[j]);
			sum += mn;
		}
		b[i] = sum;
	}
	return b;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    int mx = 0;
	int n = N;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (F[i][j]) {
				int mx = min ({(i + 1) * (j + 1), (i + 1) * (n - j), (n - i) * (j + 1), (n - i) * (n - j)});
				return n * n - mx;
			}
			if (F[i][j]) {
				u[i][j] = 0;
			} else if (i == 0) {
				u[i][j] = 1;
			} else {
				u[i][j] = u[i - 1][j] + 1;
			}
		}
	}

	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (F[i][j]) {
				d[i][j] = 0;
			} else if (i == n - 1) {
				d[i][j] = 1;
			} else {
				d[i][j] = d[i + 1][j] + 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		vector <int> A, B;
		for (int j = 0; j < n; j++) {
			A.push_back(d[i][j]);
			B.push_back(max (0, u[i][j] - 1));
		}
		vector <int> a = get (A);
		vector <int> b = get (B);
		reverse (A.begin(), A.end());
		reverse (B.begin(), B.end());
		vector <int> c = get (A);
		vector <int> e = get (B);
		reverse (c.begin(), c.end());
		reverse (e.begin(), e.end());
		for (int j = 0; j < n; j++) {
			if (F[i][j])
				continue;
			mx = max (mx, a[j] + b[j] + c[j] + e[j] - (d[i][j] + u[i][j] - 1));
		}
	}
    return mx;
}

• 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