oj.uz

답안 #355252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
355252 2021-01-22T10:44:17 Z nicolaalexandra 호화 벙커 (IZhO13_burrow) C++14
100 / 100
 1026 ms 25836 KB 
#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

# 결과 실행 시간 메모리 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