Submission #840320

#	Time	Username	Problem	Language	Result	Execution time	Memory
840320		Fysty	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	3215 ms	215440 KiB

soccer

#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

//#include "soccer.h"

//int dp[505][505][505];
map<pair<int,pii>,int > dp;
int sum[2005][2005];
int n;

int qry(int lx,int rx,int ly,int ry){return sum[rx][ry]-sum[lx-1][ry]-sum[rx][ly-1]+sum[lx-1][ly-1];}

pii extend(int pos,int l,int r)
{
    pii ans;
    int ql=1,qr=pos;
    while(ql<qr)
    {
        int mid=ql+qr>>1;
        if(qry(mid,pos-1,l,r)>0) ql=mid+1;
        else qr=mid;
    }
    ans.F=ql;
    ql=pos,qr=n;
    while(ql<qr)
    {
        int mid=ql+qr+1>>1;
        if(qry(pos+1,mid,l,r)>0) qr=mid-1;
        else ql=mid;
    }
    ans.S=ql;
    return ans;
}

int calc(int pos,int l,int r)
{
    //cout<<pos<<" "<<l<<" "<<r<<"\n";
    //if(dp[pos][l][r]!=0)
    if(dp.find({pos,{l,r}})!=dp.end()) return dp[{pos,{l,r}}];
    pii tmp=extend(pos,l,r);
    if(tmp.F<pos)
    {
        return dp[{pos,{l,r}}]=calc(tmp.F,l,r);
        //cout<<pos<<" "<<l<<" "<<r<<": "<<dp[pos][l][r]<<"\n";
        //return dp[pos][l][r];
    }
    int mx=0;
    int cur=l;
    for(int i=l;i<=r;i++)
    {
        cur=max(cur,i);

        int ql=cur-1,qr=r;
        while(ql<qr)
        {
            int mid=ql+qr+1>>1;
            bool valid=0;
            if(pos>1&&qry(pos-1,pos-1,i,mid)==0) valid=1;
            if(tmp.S+1<=n&&qry(tmp.S+1,tmp.S+1,i,mid)==0) valid=1;
            if(valid) ql=mid;
            else qr=mid-1;
        }
        if(ql>=cur) mx=max(mx,calc(pos,i,ql)-(tmp.S-tmp.F+1)*(ql-i+1));
        cur=ql+1;
    }
    return dp[{pos,{l,r}}]=mx+(tmp.S-tmp.F+1)*(r-l+1);
    //cout<<pos<<" "<<l<<" "<<r<<": "<<dp[pos][l][r]<<"\n";
    //return dp[pos][l][r];
}

int biggest_stadium(int N,vector<vector<int> > F)
{
    n=N;
    rep1(i,n)
    {
        rep1(j,n)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+F[i-1][j-1];
        }
    }
    int ans=0;
    rep1(i,n)
    {
        ll cur=1;
        while(cur<=n)
        {
            while(cur<=n&&F[i-1][cur-1]==1) cur++;
            if(cur>n) break;
            int to=cur;
            while(to+1<=n&&F[i-1][to]==0) to++;
            ans=max(ans,calc(i,cur,to));
            cur=to+1;
        }
    }
    return ans;
}

Compilation message (stderr)

soccer.cpp: In function 'pii extend(int, int, int)':
soccer.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid=ql+qr>>1;
      |                 ~~^~~
soccer.cpp:64:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid=ql+qr+1>>1;
      |                 ~~~~~^~
soccer.cpp: In function 'int calc(int, int, int)':
soccer.cpp:93:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int mid=ql+qr+1>>1;
      |                     ~~~~~^~

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