Submission #1228964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228964		toast12	Luxury burrow (IZhO13_burrow)	C++20	100 / 100	624 ms	12308 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++) {
            vector<int> left(m+1), right(m+1, m+1);
            stack<int> st;
            for (int j = 1; j <= m; j++) {
                while (!st.empty() && b[i][st.top()] > b[i][j]) {
                    right[st.top()] = j;
                    st.pop();
                }
                st.push(j);
            }
            while (!st.empty()) st.pop();
            for (int j = m; j >= 1; j--) {
                while (!st.empty() && b[i][st.top()] > b[i][j]) {
                    left[st.top()] = j;
                    st.pop();
                }
                st.push(j);
            }
            for (int j = 1; j <= m; j++) {
                if ((right[j]-left[j]-1)*b[i][j] >= k) {
                    mx_size = max(mx_size, 1ll*(right[j]-left[j]-1)*b[i][j]);
                }
            }
        }
        if (mx_size) lo = mid, sz = mx_size;
        else hi = mid-1;
    }
    cout << lo << ' ' << sz << '\n';
    return 0;
}

• Subtask 1: 100 / 100