Submission #355252

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
355252	2021-01-22T10:44:17 Z	nicolaalexandra	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1026 ms	25836 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	1 ms	748 KB	Output is correct
6	Correct	1 ms	876 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	6 ms	1516 KB	Output is correct
9	Correct	14 ms	2924 KB	Output is correct
10	Correct	40 ms	3180 KB	Output is correct
11	Correct	68 ms	4204 KB	Output is correct
12	Correct	28 ms	6636 KB	Output is correct
13	Correct	46 ms	2156 KB	Output is correct
14	Correct	90 ms	6380 KB	Output is correct
15	Correct	108 ms	6380 KB	Output is correct
16	Correct	146 ms	6764 KB	Output is correct
17	Correct	80 ms	7916 KB	Output is correct
18	Correct	377 ms	11884 KB	Output is correct
19	Correct	309 ms	12396 KB	Output is correct
20	Correct	733 ms	17960 KB	Output is correct
21	Correct	780 ms	20588 KB	Output is correct
22	Correct	1026 ms	25816 KB	Output is correct
23	Correct	1018 ms	25836 KB	Output is correct
24	Correct	476 ms	17516 KB	Output is correct
25	Correct	401 ms	19072 KB	Output is correct