Submission #1087046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087046		ainta	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	4573 ms	112672 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}


template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;
template<> const Mint Mint::G = Mint(3);
#include "soccer.h"

#define N_ 2010

int Up[N_][N_], Down[N_][N_], n, D[N_][N_], uu[N_][N_], dd[N_][N_];
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n = N;
    rep(i,n){
        rep(j,n){
            if(F[i][j]){
                Up[i][j]=i;
                Down[i][j]=i;
            }
            else{
                if(i) Up[i][j]=Up[i-1][j];
                else Up[i][j] = -1;
            }
        }
    }
    per(i,n){
        rep(j,n){
            if(!F[i][j]){
                if(i==n-1)Down[i][j]=n;
                else Down[i][j] = Down[i+1][j];
            }
        }
    }
    int res=0;
    rep(i,n){
        rng(len,0,n-1){
            rep(b,n-len){
                int e = b+len;
                if(!len){
                    if(F[i][b])D[b][e]=-1;
                    else{
                        uu[b][e] = Up[i][b];
                        dd[b][e] = Down[i][b];
                        D[b][e]=dd[b][e]-uu[b][e]-1;
                    }
                }
                else{
                    if(D[b][e-1]==-1 || D[b+1][e]==-1){
                        D[b][e]=-1;
                        continue;
                    }
                    uu[b][e] = max(uu[b][e-1],uu[b+1][e]);
                    dd[b][e] = min(dd[b][e-1],dd[b+1][e]);
                    D[b][e] = max(D[b][e-1], D[b+1][e]) + dd[b][e]-uu[b][e]-1;
                }
                res=max(res,D[b][e]);
            }
        }
    }
    return res;
}

• 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