Submission #1087326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087326		urd05	Soccer Stadium (IOI23_soccer)	C++17	70 / 100	4575 ms	390724 KiB

soccer

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

int n;
int arr[2001][2001];
typedef pair<int,int> P;
typedef pair<P,P> PP;
map<long long,int> mp;
int psum[2001][2001];
int ri[2001][2001];
int ntr[2001][2001];
const long long three=1e12;
const long long two=1e8;
const long long one=1e4;

int query(int u,int d,int l,int r) {
    return psum[d][r]-psum[u-1][r]-psum[d][l-1]+psum[u-1][l-1];
}

long long hhash(PP x) {
    return x.first.first*three+x.first.second*two+x.second.first*one+x.second.second;
}

PP unhash(long long x) {
    PP ret;
    ret.second.second=x%(n+1);
    x/=n+1;
    ret.second.first=x%(n+1);
    x/=n+1;
    ret.first.second=x%(n+1);
    x/=n+1;
    ret.first.first=x%(n+1);
    return ret;
}

int ans(int l,int r,int u,int d) {
    long long nw=hhash(PP(P(l,r),P(u,d)));
    if (mp.find(nw)!=mp.end()) {
        return mp[nw];
    }
    int now=l;
    int ret=(d-u+1)*(r-l+1);
    if (u>1) {
        while (now<=r) {
            if (arr[u-1][now]==1)
            now=ntr[u-1][now];
            if (now>r) {
                break;
            }
            int ll=now;
            int rr=min(ri[u-1][now],r);
            int uu=u;
            int dd=d;
            if (ll<=rr) {
                int lo=0;
                int hi=u;
                int val=psum[u-1][rr]-psum[u-1][ll-1];
                while (lo+1<hi) {
                    int mid=(lo+hi)/2;
                    if (-psum[mid-1][rr]+psum[mid-1][ll-1]==-val) {
                        hi=mid;
                    }
                    else {
                        lo=mid;
                    }
                }
                uu=hi;
                ret=max(ret,ans(ll,rr,uu,dd)+(r-l-rr+ll)*(d-u+1));
            }
            now=ri[u-1][now]+1;
        }
    }
    now=l;
    if (d<n) {
        while (now<=r) {
            if (arr[d+1][now]==1)
            now=ntr[d+1][now];
            if (now>r) {
                break;
            }
            int ll=now;
            int rr=min(ri[d+1][now],r);
            int uu=u;
            int dd=d;
            if (ll<=rr) {
                int lo=d;
                int hi=n+1;
                int val=-psum[d][rr]+psum[d][ll-1];
                while (lo+1<hi) {
                    int mid=(lo+hi)/2;
                    if (psum[mid][rr]-psum[mid][ll-1]==-val) {
                        lo=mid;
                    }
                    else {
                        hi=mid;
                    }
                }
                dd=lo;
                ret=max(ret,ans(ll,rr,uu,dd)+(r-l-rr+ll)*(d-u+1));
            }
            now=ri[d+1][now]+1;
        }
    }
    return mp[nw]=ret;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            arr[i+1][j+1]=F[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        int pr=0;
        for(int j=1;j<=n;j++) {
            if (arr[i][j]==1) {
                for(int k=pr+1;k<j;k++) {
                    ri[i][k]=j-1;
                }
                pr=j;
            }
        }
        for(int j=pr+1;j<=n;j++) {
            ri[i][j]=n;
        }
        pr=1;
        for(int j=1;j<=n;j++) {
            if (arr[i][j]==0) {
                for(int k=pr;k<j;k++) {
                    ntr[i][k]=j;
                }
                pr=j;
            }
        }
        for(int k=pr;k<=n;k++) {
            ntr[i][k]=n+1;
        }
    }
    int ret=0;
    for(int i=1;i<=n;i++) {
        int pr=0;
        for(int j=1;j<=n;j++) {
            if (arr[i][j]==1) {
                if (pr+1<=j-1) {
                    ret=max(ret,ans(pr+1,j-1,i,i));
                }
                pr=j;
            }
        }
        if (pr!=n) {
            ret=max(ret,ans(pr+1,n,i,i));
        }
    }
    return ret;
}

• 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: 0 / 30