| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1054459 | Ahmed57 | 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 "bits/stdc++.h"
using namespace std;
#define int long long
map<int,int> dp[501][501][501];
int n;
vector<pair<int,int>> rngs[31];
int solve(int l,int r,int x,int y){
if(l==0&&r==n-1)return 0;
if(dp[l][r][x].find(y)!=dp[l][r][x].end())return dp[l][r][x][y];
int ma = 0;
if(l){
for(auto j:rngs[l-1]){
if(max(x,j.first)<=min(y,j.second)){
ma = max(ma,solve(l-1,r,max(x,j.first),min(y,j.second))+(min(y,j.second)-max(x,j.first)+1));
}
}
}if(r<n-1){
for(auto j:rngs[r+1]){
if(max(x,j.first)<=min(y,j.second)){
ma = max(ma,solve(l,r+1,max(x,j.first),min(y,j.second))+(min(y,j.second)-max(x,j.first)+1));
}
}
}
return dp[l][r][x][y] = ma;
}
int biggest_stadium(int N, vector<vector<int>> v){
memset(dp,-1,sizeof dp);
n = N;
for(int i = 0;i<N;i++){
int la = 0;
for(int j = 0;j<N;j++){
if(v[i][j]==0){
if(la==-1)la = j;
}else{
if(la<j&&la!=-1)rngs[i].push_back({la,j-1});
la = -1;
}
}
if(la!=-1)rngs[i].push_back({la,N-1});
}
int all = 0;
for(int i = 0;i<N;i++){
for(auto j:rngs[i]){
all= max(all,solve(i,i,j.first,j.second)+(j.second-j.first+1));
}
}
return all;
}