Submission #1213169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213169		Aviansh	Soccer Stadium (IOI23_soccer)	C++20	48 / 100	4611 ms	359560 KiB

soccer

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

using namespace std;
const int maxn = 505;
int lef[maxn][maxn];
int rig[maxn][maxn];
unordered_map<string,int>mem;
int n;

string create(int a, int b, int c, int d){
    string ans = to_string(a)+":"+to_string(b)+":"+to_string(c)+":"+to_string(d);
    return ans;
}

int dp(int t, int b, int l, int r){

    if(mem.find(create(t,b,l,r))!=mem.end()){
        return mem[create(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[create(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