Submission #355252

#	Time	Username	Problem	Language	Result	Execution time	Memory
355252		nicolaalexandra	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1026 ms	25836 KiB

burrow

#include <bits/stdc++.h>
#define DIM 1010
using namespace std;

int a[DIM][DIM],v[DIM][DIM],dp_up[DIM][DIM],st[DIM],dr[DIM],w[DIM*DIM];
deque <int> d;
int n,m,i,j,maxi,k;

int solve (int val){
    int i,j;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            a[i][j] = (v[i][j] >= val) ? (1) : (0);

    /// dreptunghi de arie maxima
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            if (a[i][j])
                dp_up[i][j] = 1 + dp_up[i-1][j];
            else dp_up[i][j] = 0;
        }

    int sol = 0;
    for (i=1;i<=n;i++){

        d.clear();
        int last_poz = 0;
        for (j=1;j<=m;j++){

            if (!dp_up[i][j]){
                d.clear();
                last_poz = j;
                continue;
            }

            while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
                d.pop_back();

            if (!d.empty())
                st[j] = d.back();
            else st[j] = last_poz;

            d.push_back(j);
        }

        d.clear(); last_poz = m+1;
        for (j=m;j;j--){
            if (!dp_up[i][j]){
                d.clear();
                last_poz = j;
                continue;
            }

            while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
                d.pop_back();

            if (!d.empty())
                dr[j] = d.back();
            else dr[j] = last_poz;

            d.push_back(j);
        }

        for (j=1;j<=m;j++)
            sol = max (sol,dp_up[i][j] * (dr[j] - st[j] - 1));
    }

    return sol;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>maxi;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            cin>>v[i][j];
            w[++k] = v[i][j];
        }
    }

    sort (w+1,w+k+1);

    int el = 1;
    for (i=2;i<=k;i++){
        if (w[i] != w[i-1])
            w[++el] = w[i];
    }
    k = el;

    int st = 1, dr = k, sol = 0, arie = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        int val = solve(w[mid]);

        if (val >= maxi){
            sol = w[mid], arie = val;
            st = mid+1;
        } else dr = mid-1;
    }


    cout<<sol<<" "<<arie;

    return 0;
}

• Subtask 1: 100 / 100