제출 #685268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685268		Summers	호화 벙커 (IZhO13_burrow)	C++14	100 / 100	1177 ms	17448 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<=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+1;
        else ri=mid-1;
    }
    le--;
    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;;

}

컴파일 시 표준 에러 (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