Submission #1054471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054471		Ahmed57	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4621 ms	897380 KiB

soccer

#include "bits/stdc++.h"

using namespace std;
map<pair<int,int>,int> dp[501][501];
int n;
vector<pair<int,int>> rngs[501];
int solve(int l,int r,int x,int y){
    if(l==0&&r==n-1)return 0;
    if(dp[l][r].find(make_pair(x,y))!=dp[l][r].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){
    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;
}

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