Submission #1242237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242237		a4n_	Soccer Stadium (IOI23_soccer)	C++20	64 / 100	4597 ms	115320 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, a[2005][2005], uu[2005][2005], dd[2005][2005], ans, cnt[2005][2055];

int dp[2005][2005];
pii mn[2005][2005];
void solve(vector<pii> vec) {
    for(int i=1; i<=size(vec); i++) {
        mn[i][i].F = vec[i-1].F;
        mn[i][i].S = vec[i-1].S;
        dp[i][i] = mn[i][i].S - mn[i][i].F + 1;
    }
    for(int sz=2; sz<=size(vec); sz++) {
        for(int l,r=sz; r<=size(vec); r++) {
            l = r - sz + 1;
            mn[l][r].F = max(mn[l+1][r].F, mn[l][r-1].F);
            mn[l][r].S = min(mn[l+1][r].S, mn[l][r-1].S);
            dp[l][r] = max(dp[l+1][r], dp[l][r-1]) + max(mn[l][r].S - mn[l][r].F + 1, 0);
        }
    }

    ans = max(ans, dp[1][size(vec)]);
}

int biggest_stadium(int _N, vector<vector<int>> F) {
    n = _N;

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            a[i][j] = F[i-1][j-1];
        }
    }

    for(int i=1; i<=n; i++) uu[1][i] = 1;
    for(int i=2; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(a[i-1][j] == 0) uu[i][j] = uu[i-1][j];
            else uu[i][j] = i;
        }
    }

    for(int i=1; i<=n; i++) dd[n][i] = n;
    for(int i=n-1; i>=1; i--) {
        for(int j=1; j<=n; j++) {
            if(a[i+1][j] == 0) dd[i][j] = dd[i+1][j];
            else dd[i][j] = i;
        }
    }

    for(int i=1; i<=n; i++) {
        vector<pii> vec;
        for(int j=1; j<=n; j++) {
            if(a[i][j] == 1) {
                solve(vec);
                vec.clear();
            } else {
                vec.pb({uu[i][j], dd[i][j]});
            }
        }
        solve(vec);
    }

    return ans;
}

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