//#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 505;
void upMax(int &x, int y) {
x = max(x, y);
}
int sub1(int N, vector<vector<int>> F) {
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++) {
if(F[i][j] == 1) {
return max({
N * i + N * j - i * j,
N * i + N * (N - j - 1) - i * (N - j - 1),
N * (N - i - 1) + N * j - (N - i - 1) * j,
N * (N - i - 1) + N * (N - j - 1) - (N - i - 1) * (N - j - 1)
});
}
}
}
return N * N;
}
map<int, int> low[mxN][mxN];
int sub5(int N, vector<vector<int>> F) {
vector<vector<int>> sum(N, vector<int> (N, 0)), high(N, vector<int> (N, 0));
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++) {
sum[i][j] = (j ? sum[i][j - 1] : 0) + F[i][j];
}
}
auto get_sum = [&] (int row, int l, int r) {
return sum[row][r] - (!l ? 0 : sum[row][l - 1]);
};
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++) {
high[i][j] = (F[i][j] ? 0 : (i ? high[i - 1][j] : 0) + 1);
}
}
for(int i = 0; i < N; i ++) {
for(int k = 0; k < N; k ++) {
int x = high[i][k];
for(int j = k; j >= 0; j --) {
x = min(x, high[i][j]);
low[i][j][k] = x;
}
}
}
vector<vector<int>> dp(N, vector<int> (N, 0));
int result = 0;
for(int row = 0; row < N; row ++) {
for(int i = 0; i < N; i ++) {
for(int j = i; j < N; j ++) {
if(get_sum(row, i, j)) dp[i][j] = 0;
}
}
for(int i = 0, j = 0; i < N; i = j + 1) {
for(j = i; j + 1 < N && F[row][j + 1] == F[row][i]; ) j ++ ;
if(F[row][i]) continue ;
for(int k = (j - i + 1); k > 0; k --) {
for(int l = i; l + k - 1 <= j; l ++) {
int r = l + k - 1;
if(k > 1) {
if(l + 1 < N) upMax(dp[l + 1][r], dp[l][r] + low[row][l][r]);
if(r - 1 >= 0) upMax(dp[l][r - 1], dp[l][r] + low[row][l][r]);
} else {
upMax(result, dp[l][r] + low[row][l][r]);
}
}
}
}
}
return result;
}
int biggest_stadium(int N, vector<vector<int>> F) {
if(N <= 500) return sub5(N, F);
return sub1(N, F);
}
int main() {
#define taskname "test"
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
int N;
cin >> N;
vector<vector<int>> F(N, vector<int> (N));
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++) {
cin >> F[i][j];
}
}
cout << biggest_stadium(N, F) << "\n";
return 0;
}
Compilation message
soccer.cpp: In function 'int main()':
soccer.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccnVZ9y8.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXB88s8.o:soccer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
