Submission #1240486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240486		dosts	Soccer Stadium (IOI23_soccer)	C++20	54 / 100	1156 ms	2162688 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 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;
        }
    }

    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;
}

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