Submission #973262

#	Time	Username	Problem	Language	Result	Execution time	Memory
973262		raphaelp	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	849 ms	55980 KiB

soccer

#include<bits/stdc++.h>
using namespace std;
int biggest_stadium(int N, vector<vector<int>> F)
{
    vector<vector<int>> Nextleft(N+1, vector<int>(N+1, -1));
    vector<int> dp(N+1, 0), sz(N+1, 0);
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            if (F[i][j]==1)Nextleft[i][j]=j;
            else if (j>0)Nextleft[i][j]=Nextleft[i][j-1];
        }
    }
    int maxx=0;
    for (int Right=N-1; Right>=0; Right--)
    {
        vector<int> haut(N+1), bas(N+1),cursize(N+1);
        for (int i=0; i<N; i++)
        {
            haut[i]=i;
            bas[i]=i;
        }
        vector<int> ST;
        for (int i=0; i<N; i++)
        {
            int last=i;
            while(!ST.empty() && Nextleft[i][Right]>=Nextleft[ST.back()][Right])
            {
                last=ST.back();
                ST.pop_back();
            }
            ST.push_back(i);
            haut[i]=haut[last];
        }
        ST.clear();
        for (int i=N-1; i>=0; i--)
        {
            int last=i;
            while(!ST.empty() && Nextleft[i][Right]>=Nextleft[ST.back()][Right])
            {
                last=ST.back();
                ST.pop_back();
            }
            ST.push_back(i);
            bas[i]=bas[last];
            cursize[i]=bas[i]-haut[i]+1;
        }
        vector<pair<int,int>> rectangles;
        vector<int> l(N+1,-1), r(N+1, -1);
        for (int i=0; i<N;i ++)
        {
            l[i]=i-1;
            r[i]=i+1;
            if (!F[i][Right])rectangles.push_back({Nextleft[i][Right], i});
        }
        r[N-1]=-1;
        sort(rectangles.begin(), rectangles.end());
        for (int i=rectangles.size()-1; i>=0; i--)
        {
            int x=rectangles[i].second;
            dp[x]+=(cursize[x]-sz[x])*(Right-Nextleft[x][Right]);
        }
        for (int i=0; i<rectangles.size(); i++)
        {
            int x=rectangles[i].second;
            if (r[x]!=-1)dp[r[x]]=max(dp[r[x]], dp[x]+((cursize[r[x]]-cursize[x])*(Right-Nextleft[r[x]][Right])));
            if (l[x]!=-1)dp[l[x]]=max(dp[l[x]], dp[x]+((cursize[l[x]]-cursize[x])*(Right-Nextleft[l[x]][Right])));
            if (r[x]!=-1)l[r[x]]=l[x];
            if (l[x]!=-1)r[l[x]]=r[x];
            sz[x]=cursize[x];
        }
        for (int i=0; i<N; i++)
        {
            if (F[i][Right]==1)
            {
                maxx=max(maxx, dp[i]);
                dp[i]=0;
                sz[i]=0;
            }
        }
    }
    for (int i=0; i<N; i++)maxx=max(maxx, dp[i]);
    return maxx;
}

/* int main()
{
    int N;
    cin >> N;
    vector<vector<int>> F(N, vector<int>(N));
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            cin >> F[i][j];
        }
    }
    cout << biggest_stadium(N, F);
} */

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i=0; i<rectangles.size(); i++)
      |                       ~^~~~~~~~~~~~~~~~~~

• 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