Submission #343282

#	Time	Username	Problem	Language	Result	Execution time	Memory
343282		apostoldaniel854	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	666 ms	18028 KiB

burrow

#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 / 100