Submission #1029816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029816		lucri	Soccer Stadium (IOI23_soccer)	C++17	1.50 / 100	1603 ms	210000 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
int n,next[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;
void adauga(int up,int down,int l,int r,int valac)
{
    std::pair<std::pair<int,int>,std::pair<int,int>>cod={{up,down},{l,r}};
    if(val.find(cod)==val.end())
    {
        q.push({down-up,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=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: 1.5 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30