제출 #1228923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228923		toast12	호화 벙커 (IZhO13_burrow)	C++20	0 / 100	0 ms	328 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()) {
                    if (s.top().first == b[i][j]) {
                        if ((j-s.top().second+1)*b[i][j] >= k) {
                            mx_size = max(mx_size, 1ll*(j-s.top().second+1)*b[i][j]);
                        }
                    }
                    else s.push({b[i][j], j});
                }
                else 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