Submission #1304861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304861		domi	Luxury burrow (IZhO13_burrow)	C++20	100 / 100	452 ms	16200 KiB

burrow

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e3;
const int VMAX = 1e9;

using namespace std;

int aux[NMAX + 5][NMAX + 5], h[NMAX + 5], l[NMAX + 5], r[NMAX + 5];
int mat[NMAX + 5][NMAX + 5], n, m, k;

int check(int val) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            aux[i][j] = (mat[i][j] >= val);
    }

    int ans = INT_MIN;
    fill(h + 1, h + m + 1, 0LL);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            h[j] = (aux[i][j] ? h[j] + 1 : 0);

        stack<int>st;
        for (int j = 1; j <= m; ++j) {
            while (!st.empty() && h[j] <= h[st.top()])
                st.pop();

            l[j] = (st.empty() ? 0 : st.top());
            st.push(j);
        }

        stack<int>dr;
        for (int j = m; j >= 1; --j) {
            while (!dr.empty() && h[j] <= h[dr.top()])
                dr.pop();

            r[j] = (dr.empty() ? m + 1 : dr.top());
            dr.push(j);
        }

        for (int j = 1; j <= m; ++j)
            ans = max(ans, h[j] * (r[j] - l[j] - 1));
    }

    return ans;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> k;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            cin >> mat[i][j];
    }

    int lo = 1, hi = VMAX, ans = 0;
    while (lo <= hi) {
        auto mid = (lo + hi) >> 1;

        if (check(mid) >= k) {
            ans = mid;
            lo = mid + 1;
        }
        else
            hi = mid - 1;
    }

    cout << ans << ' ' << check(ans) << '\n';
    return 0;
}

• Subtask 1: 100 / 100