| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1059909 | tolbi | Soccer Stadium (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
int dp[2][N][N][N]={};
int ans = 0;
for (int l = 0; l < N; l++){
for (int r = l; r < N; r++){
dp[0][N-1][l][r]=r-l+1;
for (int i = l; i <= r; i++){
if (F[N-1][i]==1){
dp[0][N-1][l][r]=0;
break;
}
}
dp[1][N-1][l][r]=dp[0][N-1][l][r];
ans=max(ans,dp[1][N-1][l][r]);
}
}
for (int i = N-2; i >= 0; i--){
for (int l = 0; l < N; l++){
for (int r = N-1; r >= l; r--){
dp[0][i][l][r]=r-l+1;
for (int j = l; j <= r; j++){
if (F[i][j]==1){
dp[0][i][l][r]=0;
break;
}
}
if (dp[0][i][l][r]==0) {
dp[1][i][l][r]=0;
continue;
}
int cur = 0;
int lel = l;
for (int j = l; j <= r; j++){
if (F[i+1][j]==0){
cur=max(cur,dp[0][i+1][lel][j]);
}
else {
lel=j+1;
}
}
dp[0][i][l][r]+=cur;
dp[1][i][l][r]=dp[0][i][l][r];
if (l>0){
dp[1][i][l][r]=max(dp[1][i][l][r],dp[1][i][l-1][r]);
}
if (r+1<N){
dp[1][i][l][r]=max(dp[1][i][l][r],dp[1][i][l][r+1]);
}
dp[1][i][l][r]=max(dp[1][i][l][r],r-l+1+dp[1][i+1][l][r]);
ans=max(ans,dp[1][i][l][r]);
}
}
}
return ans;
}