Submission #685266

#	Time	Username	Problem	Language	Result	Execution time	Memory
685266		Summers	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1123 ms	27052 KiB

burrow

#include<bits/stdc++.h>
#include<stack>
#define endl '\n'
using namespace std;
long long n,m,k,num=0, a[1002][1002], s[1002][1002], b[1002];
stack< pair<long long,long long> >l[1002],r[1002];
long long ll[1003], rr[1003];
long long maxar()
{
    num++;
    long long i,j, ans=-1;

    for(j=1;j<=m;j++)b[j]=s[1][j];

    for(j=1;j<=m;j++)
    {
        while(!l[num].empty() && l[num].top().first>=b[j])
        {
            l[num].pop();
        }
        if(!l[num].empty())ll[j]=l[num].top().second;
        else ll[j]=0;

        l[num].push({b[j],j});
    }
    for(j=m;j>=1;j--)
    {
        while(!r[num].empty() && r[num].top().first>=b[j])
        {
            r[num].pop();
        }
        if(!r[num].empty())rr[j]=r[num].top().second;
        else rr[j]=m+1;

        r[num].push({b[j],j});
    }

    for(j=1;j<=m;j++)
    {
        ans=max(ans, b[j]*(rr[j]-ll[j]-1));
    }

    for(i=2;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(s[i][j]==0)b[j]=0;
            else b[j]++;
        }
        while(!l[num].empty())l[num].pop();
        while(!r[num].empty())r[num].pop();

         for(j=1;j<=m;j++)
        {
        while(!l[num].empty() && l[num].top().first>=b[j])
        {
            l[num].pop();
        }
        if(!l[num].empty())ll[j]=l[num].top().second;
        else ll[j]=0;

        l[num].push({b[j],j});

    }
    for(j=m;j>=1;j--)
    {
        while(!r[num].empty() && r[num].top().first>=b[j])
        {
            r[num].pop();
        }
        if(!r[num].empty())rr[j]=r[num].top().second;
        else rr[j]=m+1;

        r[num].push({b[j],j});
    }

    for(j=1;j<=m;j++)
    {
        ans=max(ans, b[j]*(rr[j]-ll[j]-1));
    }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j,b,c,le,ri,mid,mini=1000000000000,maxi=0;

    cin>>n>>m>>k;

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>a[i][j];
            mini=min(mini, a[i][j]);
            maxi=max(maxi, a[i][j]);
        }
    }
    le=mini; ri=maxi+10;

    while(le+1<ri)
    {
        mid=(le+ri)/2;

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(a[i][j]>=mid)s[i][j]=1;
                else s[i][j]=0;
            }
        }

        c=maxar();
        if(c>=k)le=mid;
        else ri=mid;
    }
    for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(a[i][j]>=le)s[i][j]=1;
                else s[i][j]=0;
            }
        }

        c=maxar();
    cout<<le<<" "<<c<<endl;;

}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:91:19: warning: unused variable 'b' [-Wunused-variable]
   91 |     long long i,j,b,c,le,ri,mid,mini=1000000000000,maxi=0;
      |                   ^

• Subtask 1: 100 / 100