Submission #895991

#	Time	Username	Problem	Language	Result	Execution time	Memory
895991		heeheeheehaaw	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	486 ms	18256 KiB

burrow

#include <bits/stdc++.h>

using namespace std;

int a[1005][1005];
int sp[1005][1005];
int n, m, k;
int hei[1005];
int st[1005], dr[1005];

int partsum(int x1, int x2, int y1, int y2)
{
    return sp[x2][y2] - sp[x2][y1 - 1] - sp[x1 - 1][y2] + sp[x1 - 1][y1 - 1];
}

int calcarie(int x1, int x2, int y1, int y2)
{
    return (x2 - x1 + 1) * (y2 - y1 + 1);
}

int solve(int minn)
{
    int maxx = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            sp[i][j] = 0;
            if(a[i][j] >= minn)
                sp[i][j] = 1;
            hei[j] = 0;
        }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(sp[i][j] == 1) hei[j]++;
            else hei[j] = 0;
        }

        stack<int> s;
        for(int j = 1; j <= m; j++)
        {
            while(!s.empty() && hei[s.top()] >= hei[j])
                s.pop();
            if(s.empty()) st[j] = 0;
            else st[j] = s.top();
            s.push(j);
        }

        s = stack<int>{};
        for(int j = m; j >= 1; j--)
        {
            while(!s.empty() && hei[s.top()] >= hei[j])
                s.pop();
            if(s.empty()) dr[j] = m + 1;
            else dr[j] = s.top();
            s.push(j);
        }

        for(int j = 1; j <= m; j++)
            maxx = max(maxx, hei[j] * (dr[j] - st[j] - 1));
    }

    return maxx;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>a[i][j];
    int st = 1, dr = 1e9, rez = 0, poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        int maxx = solve(mij);

        if(maxx >= k)
            poz = mij, rez = maxx, st = mij + 1;
        else
            dr = mij - 1;
    }

    cout<<poz<<" "<<rez<<'\n';
    return 0;
}

• Subtask 1: 100 / 100