oj.uz

Submission #49778

# Submission time Handle Problem Language Result Execution time Memory
49778 2018-06-03T02:48:52 Z mra2322001 Luxury burrow (IZhO13_burrow) C++14
100 / 100
 1141 ms 62528 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)

using namespace std;
typedef long long ll;
const int N = 1002;

int m, n, a[N][N], d[N][N], b[N], l[N], r[N], arr[N][N], k;
vector <int> save;

int check(int x){
    f1(i, m) f1(j, n){
        d[i][j] = 0;
        if(arr[i][j] >= x) a[i][j] = 1;
        else a[i][j] = 0;
    }
    f1(i, m){
        for(int j = n; j>= 1; j--){
            if(!a[i][j]) d[i][j] = 0;
            else{
                d[i][j] = d[i][j + 1] + 1;
            }
         }
    }
    int res = 0;
    f1(j, n){
        f1(i, m) b[i] = d[i][j], l[i] = r[i] = 0;
        stack <int> s;
        f1(i, m){
            while(s.size() && b[s.top()] >= b[i]) s.pop();
            if(s.size()) l[i] = s.top() + 1;
            else l[i] = 1;
            s.push(i);
        }
        while(s.size()) s.pop();
        for(int i = m; i >= 1; i--){
            while(s.size() && b[s.top()] >= b[i]) s.pop();
            if(s.size()) r[i] = s.top() - 1;
            else r[i] = m;
            s.push(i);
        }
        f1(i, m){
            res = max(res, b[i] * (r[i] - l[i] + 1));
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
  
    cin >> m >> n >> k;
    f1(i, m) f1(j, n) cin >> arr[i][j], save.push_back(arr[i][j]);
    sort(save.begin(), save.end());
    int lo = 0, ri = save.size() - 1;
    int ans1 = 0, ans2 = 0;
    while(lo <= ri){
        int mid = (lo + ri)/2;
        int g = check(save[mid]);
        if(g >= k) ans1 = save[mid], ans2 = g, lo = mid + 1;
        else ri = mid - 1;
    }
    cout << ans1 << " " << ans2;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 2 ms 548 KB Output is correct
4 Correct 3 ms 696 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 996 KB Output is correct
7 Correct 3 ms 996 KB Output is correct
8 Correct 13 ms 2068 KB Output is correct
9 Correct 22 ms 3572 KB Output is correct
10 Correct 37 ms 3856 KB Output is correct
11 Correct 63 ms 5192 KB Output is correct
12 Correct 49 ms 8228 KB Output is correct
13 Correct 54 ms 8228 KB Output is correct
14 Correct 169 ms 8460 KB Output is correct
15 Correct 170 ms 9000 KB Output is correct
16 Correct 143 ms 10108 KB Output is correct
17 Correct 192 ms 12160 KB Output is correct
18 Correct 418 ms 16564 KB Output is correct
19 Correct 610 ms 20104 KB Output is correct
20 Correct 853 ms 27464 KB Output is correct
21 Correct 844 ms 35600 KB Output is correct
22 Correct 1117 ms 47220 KB Output is correct
23 Correct 1141 ms 56844 KB Output is correct
24 Correct 994 ms 58060 KB Output is correct
25 Correct 945 ms 62528 KB Output is correct