Submission #882519

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882519	2023-12-03T10:00:55 Z	alexdd	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	737 ms	13952 KB

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

#	Verdict	Execution time	Memory	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