Submission #882519

#	Time	Username	Problem	Language	Result	Execution time	Memory
882519		alexdd	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	737 ms	13952 KiB

burrow

#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 / 100