oj.uz

답안 #685268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685268 2023-01-23T19:43:11 Z Summers 호화 벙커 (IZhO13_burrow) C++14
100 / 100
 1177 ms 17448 KB 
#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;;

}

Compilation message

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 2004 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 7 ms 2644 KB Output is correct
9 Correct 11 ms 3668 KB Output is correct
10 Correct 41 ms 3900 KB Output is correct
11 Correct 87 ms 4736 KB Output is correct
12 Correct 22 ms 6464 KB Output is correct
13 Correct 60 ms 3276 KB Output is correct
14 Correct 71 ms 7460 KB Output is correct
15 Correct 80 ms 7380 KB Output is correct
16 Correct 136 ms 7460 KB Output is correct
17 Correct 53 ms 9484 KB Output is correct
18 Correct 381 ms 11212 KB Output is correct
19 Correct 245 ms 12732 KB Output is correct
20 Correct 821 ms 14308 KB Output is correct
21 Correct 755 ms 15876 KB Output is correct
22 Correct 1177 ms 17448 KB Output is correct
23 Correct 1150 ms 17428 KB Output is correct
24 Correct 405 ms 16712 KB Output is correct
25 Correct 353 ms 17408 KB Output is correct