Submission #1213162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213162		Aviansh	Soccer Stadium (IOI23_soccer)	C++20	48 / 100	4548 ms	540112 KiB

soccer

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

using namespace std;
const int maxn = 505;
int lef[maxn][maxn];
int rig[maxn][maxn];
map<array<int,4>,int>mem;
int n;
int dp(int t, int b, int l, int r){
    if(mem.find({t,b,l,r})!=mem.end()){
        return mem[{t,b,l,r}];
    }
    int ans = 0;
    //add to top. ie to t-1
    if(t){
        for(int i = l;i<=r;i++){
            if(lef[t-1][i]==rig[t-1][i])
                continue;
            int len = min(rig[t-1][i]-1,r)-max(lef[t-1][i]+1,l)+1;
            ans=max(ans,dp(t-1,b,max(lef[t-1][i]+1,l),min(rig[t-1][i]-1,r))+len);
            i=rig[t-1][i];
        }
    }
    if(b<n-1){
        for(int i = l;i<=r;i++){
            if(lef[b+1][i]==rig[b+1][i])
                continue;
            int len = min(rig[b+1][i]-1,r)-max(lef[b+1][i]+1,l)+1;
            ans=max(ans,dp(t,b+1,max(lef[b+1][i]+1,l),min(rig[b+1][i]-1,r))+len);
            i=rig[b+1][i];
        }
    }
    mem[{t,b,l,r}]=ans;
    return ans;
}

int biggest_stadium(int N, vector<vector<int>> F)
{
    n=N;
    mem.clear();
    for(int i = 0;i<n;i++){
        int las = -1;
        for(int j = 0;j<n;j++){
            if(F[i][j])
                las=j;
            lef[i][j]=las;
        }
        las=n;
        for(int j = n-1;j>=0;j--){
            if(F[i][j])
                las=j;
            rig[i][j]=las;
        }
    }
    int ans = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(lef[i][j]==rig[i][j])
                continue;
            ans=max(ans,dp(i,i,lef[i][j]+1,rig[i][j]-1)+rig[i][j]-1-lef[i][j]);
        }
    }
    return ans;
}

• 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