oj.uz

답안 #882519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882519 2023-12-03T10:00:55 Z alexdd 호화 벙커 (IZhO13_burrow) C++17
100 / 100
 737 ms 13952 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int mat[1005][1005];
int ult[1005];
int tole[1005];
int aux[1005];
int verif(int lim)
{
    int mxm=0;
    for(int i=1;i<=m;i++)
        ult[i]=0;
    for(int i=1;i<=n;i++)
    {
        deque<int> dq;
        for(int j=1;j<=m;j++)
        {
            if(mat[i][j]<lim)
                ult[j] = i;
            aux[j] = i - ult[j];
            while(!dq.empty() && aux[dq.back()]>=aux[j])
                dq.pop_back();
            if(dq.empty())
                tole[j] = 0;
            else
                tole[j] = dq.back();
            dq.push_back(j);
        }
        dq.clear();
        for(int j=m;j>0;j--)
        {
            int tori;
            while(!dq.empty() && aux[dq.back()]>=aux[j])
                dq.pop_back();
            if(dq.empty())
                tori = m+1;
            else
                tori = dq.back();
            dq.push_back(j);
            mxm = max(mxm, (tori-tole[j]-1)*aux[j]);
        }
    }
    return mxm;
}
signed main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mat[i][j];
        }
    }
    //cout<<verif(2);
    //return 0;
    int st,dr,mij;
    st=0;
    dr=1e9;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(verif(mij) >= k)
        {
            if(verif(mij+1) < k)
                break;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    cout<<mij<<" "<<verif(mij);
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 10 ms 2652 KB Output is correct
9 Correct 10 ms 2724 KB Output is correct
10 Correct 35 ms 2908 KB Output is correct
11 Correct 55 ms 3252 KB Output is correct
12 Correct 23 ms 2812 KB Output is correct
13 Correct 41 ms 2904 KB Output is correct
14 Correct 80 ms 3228 KB Output is correct
15 Correct 70 ms 3228 KB Output is correct
16 Correct 104 ms 3664 KB Output is correct
17 Correct 96 ms 3160 KB Output is correct
18 Correct 206 ms 5576 KB Output is correct
19 Correct 217 ms 5032 KB Output is correct
20 Correct 601 ms 9472 KB Output is correct
21 Correct 532 ms 10312 KB Output is correct
22 Correct 653 ms 13952 KB Output is correct
23 Correct 737 ms 13764 KB Output is correct
24 Correct 409 ms 6992 KB Output is correct
25 Correct 496 ms 7212 KB Output is correct