Submission #1240509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240509		dosts	Soccer Stadium (IOI23_soccer)	C++20	1.50 / 100	197 ms	31772 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define big(x) ((int)(x.size()))
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{   
    int ctr = 0;
    pii pos;
    for (int i=1;i<=N;i++) {
        for (int j = 1;j<=N;j++) { 
            if (F[i-1][j-1] == 1) {
                ctr++,pos = {i,j};
            }
        }
    }
/*     if (ctr == 1) {
        int i = pos.ff,j = pos.ss;
        int ans1 = (i-1)*N+(N-j)*(N-i+1);
        int ans2 = (i-1)*N+(j-1)*(N-i+1);
        int ans3 = (N-i)*N+(N-j)*(i);
        int ans4 = (N-i)*N+(j-1)*(i);
        return max({ans1,ans2,ans3,ans4});
    } */
    vector<pii> maximal[N+1];
    for (int j = 1;j<=N;j++) {
        for (int i = 1;i<=N;) {
            if (F[i-1][j-1] == 1) {
                i++;
                continue;
            }
            int cur = i;
            while (cur < N && F[cur][j-1] == 0) cur++;
            maximal[j].push_back({i,cur});
            i = cur+1;
        }
    }
    if (N <1) { 
        int dp[N+1][N+1][N+1][N+1];
        memset(dp,0,sizeof dp);
        int ans = 0;
        for (int L = N;L>=1;L--) {
            for (auto it : maximal[L]) {
                int& dpp = dp[L][L][it.ff][it.ss];
                dpp = max(dpp,it.ss-it.ff+1);
            }
            for (int  R= L; R <= N;R++) {
                for (int l = 1;l<=N;l++) {
                    for (int r = l;r <= N;r++) {
                        if (!dp[L][R][l][r]) continue;
                        ans = max(ans,dp[L][R][l][r]);
                        if (L>1) {
                            for (auto it : maximal[L-1]) {
                                int newl = max(l,it.ff),newr = min(r,it.ss);
                                if (newl > newr) continue;
                                int& dpp = dp[L-1][R][newl][newr];
                                dpp = max(dpp,dp[L][R][l][r]+newr-newl+1);
                            }
                        }
                        if (R < N) {
                            for (auto it : maximal[R+1]) {
                                int newl = max(l,it.ff),newr = min(r,it.ss);
                                if (newl > newr) continue;
                                int& dpp = dp[L][R+1][newl][newr];
                                dpp = max(dpp,dp[L][R][l][r]+newr-newl+1);
                            }                  
                        }
                    }
                }
            }
        }
        return ans;
    }
    for (int i=1;i<=N;i++) {
        if (maximal[i].size() > 1) return 0;
    }
    bool dp[N+1][N+1];
    memset(dp,0,sizeof dp);
    for (int L = N;L>=1;L--) {
        dp[L][L] = 1;
        for (int  R= L; R <= N;R++) {
            if (!dp[L][R]) continue;
            int myl = max((big(maximal[L])?maximal[L][0].ff:(N+1)),(big(maximal[R])?maximal[R][0].ff:(N+1)));
            int myr = min((big(maximal[L])?maximal[L][0].ss:0),(big(maximal[R])?maximal[R][0].ss:(0)));
            if (L > 1) {
                if (maximal[L-1].empty()) {
                    dp[L-1][R] = 1;
                    continue;
                }
                int hisl = maximal[L-1][0].ff;
                int hisr = maximal[L-1][0].ss;
                if (hisl >= myl && hisr >= myr)  {
                    dp[L-1][R] = 1;
                }
            }
            if (R < N) {
                if (maximal[R+1].empty()) {
                    dp[L][R+1] = 1;
                    continue;
                }
                int hisl = maximal[R+1][0].ff;
                int hisr = maximal[R+1][0].ss;
                if (hisl >= myl && hisr >= myr)  {
                    dp[L-1][R+1] = 1;
                }
            }
        }
    }
    if (dp[1][N]) return N*N-ctr;
    return 0;
}

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