Submission #1228931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228931		toast12	Luxury burrow (IZhO13_burrow)	C++20	0 / 100	1 ms	324 KiB

burrow

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n+2, vector<int>(m+2));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    ll lo = 0, hi = 1e9;
    ll sz = 0;
    while (lo < hi) {
        ll mid = (lo+hi+1)/2;
        vector<vector<int>> v(n+2, vector<int>(m+2));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] >= mid) v[i][j] = 1;
            }
        }
        vector<vector<int>> b(n+2, vector<int>(m+2));
        b[1] = v[1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (v[i][j]) b[i][j] = b[i-1][j]+1;
                else b[i][j] = 0;
            }
        }
        ll mx_size = 0;
        for (int i = 1; i <= n; i++) {
            stack<pair<int, int>> s;
            for (int j = 1; j <= m; j++) {
                while (!s.empty() && b[i][j] < s.top().first) s.pop();
                if (!s.empty() && s.top().first <= b[i][j]) {
                    if ((j-s.top().second+1)*s.top().first >= k) {
                        mx_size = max(mx_size, 1ll*(j-s.top().second+1)*b[i][j]);
                    }
                }
                if (s.empty() || b[i][j] > s.top().first) s.push({b[i][j], j});
            }
        }
        if (mx_size) lo = mid, sz = mx_size;
        else hi = mid-1;
    }
    cout << lo << ' ' << sz << '\n';
    return 0;
}

• Subtask 1: 0 / 100