Submission #1029823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029823		lucri	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	2206 ms	154796 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
int n,next[2010][2010],sum[2010][2010],ans;
std::map<std::pair<std::pair<int,int>,std::pair<int,int>>,int>val;
std::priority_queue<std::pair<int,std::pair<std::pair<int,int>,std::pair<int,int>>>>q;
int suma(int i,int ii,int j,int jj)
{
    return sum[ii+1][jj+1]-sum[ii+1][j]-sum[i][jj+1]+sum[i][j];
}
void adauga(int up,int down,int l,int r,int valac)
{
    int b=0,e=up-1;
    while(b<=e)
    {
        int m=(b+e)/2;
        if(suma(m,up,l,r)==0)
            e=m-1;
        else
            b=m+1;
    }
    valac+=(r-l+1)*(up-b);
    up=b;
    b=down+1,e=n-1;
    while(b<=e)
    {
        int m=(b+e)/2;
        if(suma(down,m,l,r)==0)
            b=m+1;
        else
            e=m-1;
    }
    valac+=(r-l+1)*(e-down);
    down=e;
    std::pair<std::pair<int,int>,std::pair<int,int>>cod={{up,down},{l,r}};
    if(val.find(cod)==val.end())
    {
        q.push({up-down,cod});
        val[cod]=valac;
    }
    else
        if(valac>val[cod])
            val[cod]=valac;
    if(valac>ans)
        ans=valac;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+F[i-1][j-1];
    for(int i=0;i<n;++i)
    {
        next[i][n]=n-1;
        for(int j=n-1;j>=0;--j)
        {
            if(F[i][j]==1)
                next[i][j]=j-1;
            else
                next[i][j]=next[i][j+1];
        }
    }
    for(int i=0;i<n;++i)
    {
        int poz=0;
        while(poz!=n)
        {
            if(next[i][poz]<poz)
                ++poz;
            else
            {
                adauga(i,i,poz,next[i][poz],next[i][poz]-poz+1);
                poz=next[i][poz]+1;
            }
        }
    }
    while(!q.empty())
    {
        std::pair<std::pair<int,int>,std::pair<int,int>>cod=q.top().second;
        q.pop();
        int up=cod.first.first;
        int down=cod.first.second;
        int l=cod.second.first;
        int r=cod.second.second;
        if(up)
        {
            int poz=l;
            while(poz<=r)
            {
                if(next[up-1][poz]>=poz)
                {
                    adauga(up-1,down,poz,std::min(next[up-1][poz],r),val[cod]+std::min(next[up-1][poz],r)-poz+1);
                    poz=next[up-1][poz]+1;
                }
                else
                    ++poz;
            }
        }
        if(down+1!=n)
        {
            int poz=l;
            while(poz<=r)
            {
                if(next[down+1][poz]>=poz)
                {
                    adauga(up,down+1,poz,std::min(next[down+1][poz],r),val[cod]+std::min(next[down+1][poz],r)-poz+1);
                    poz=next[down+1][poz]+1;
                }
                else
                    ++poz;
            }
        }
    }
    return ans;
}

• 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