oj.uz

Submission #343282

# Submission time Handle Problem Language Result Execution time Memory
343282 2021-01-03T15:43:26 Z apostoldaniel854 Luxury burrow (IZhO13_burrow) C++14
100 / 100
 666 ms 18028 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;
const int MAX_N = 1000;
int a[1 + MAX_N][1 + MAX_N], b[1 + MAX_N][1 + MAX_N];

int to_left[1 + MAX_N], to_right[1 + MAX_N];
int n, m;
int check (int bound) {
    for (int i = 1; i <= n; i++)
        for (int j = m; j > 0; j--)
            if (a[i][j] >= bound)
                b[i][j] = b[i][j + 1] + 1;
            else
                b[i][j] = 0;
    int best_area = 0;
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            to_left[i] = i - 1;
            while (to_left[i] && b[to_left[i]][j] >= b[i][j])
                to_left[i] = to_left[to_left[i]];
        }
        for (int i = n; i > 0; i--) {
            to_right[i] = i + 1;
            while (to_right[i] && b[to_right[i]][j] >= b[i][j])
                to_right[i] = to_right[to_right[i]];
        }
        for (int i = 1; i <= n; i++)
            best_area = max (best_area, (to_right[i] - to_left[i] - 1) * b[i][j]);
    }
    return best_area;
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int k;
    cin >> n >> m >> k;
    int mx = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j], mx = max (mx, a[i][j]);
    int lb = 1, rb = mx, best = 0;
    while (lb <= rb) {
        int mid = (lb + rb) / 2;
        if (check (mid) >= k)
            best = mid, lb = mid + 1;
        else
            rb = mid - 1;
    }
    cout << best << " " << check (best) << "\n";
    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 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 4 ms 1132 KB Output is correct
9 Correct 7 ms 2028 KB Output is correct
10 Correct 25 ms 2284 KB Output is correct
11 Correct 53 ms 3052 KB Output is correct
12 Correct 17 ms 4460 KB Output is correct
13 Correct 35 ms 1644 KB Output is correct
14 Correct 48 ms 4076 KB Output is correct
15 Correct 57 ms 4204 KB Output is correct
16 Correct 80 ms 4588 KB Output is correct
17 Correct 39 ms 4844 KB Output is correct
18 Correct 220 ms 7808 KB Output is correct
19 Correct 181 ms 7660 KB Output is correct
20 Correct 535 ms 12140 KB Output is correct
21 Correct 438 ms 13676 KB Output is correct
22 Correct 632 ms 18028 KB Output is correct
23 Correct 666 ms 17900 KB Output is correct
24 Correct 284 ms 10732 KB Output is correct
25 Correct 220 ms 10988 KB Output is correct