제출 #1346813

#제출 시각아이디문제언어결과실행 시간메모리
1346813kawhiet호화 벙커 (IZhO13_burrow)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    int l = 0, r = 2e9, ans = 0;
    while (l + 1 < r) {
        int tm = (l + r) / 2;
        vector<vector<int>> b(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                b[i][j] = (a[i][j] >= tm);
            }
        }
        vector<vector<int>> p(n, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j + 1] = p[i][j] + b[i][j];
            }
        }
        int mx = 0;
        for (int s = 1; s <= m; s++) {
            for (int j = 0; j + s <= m; j++) {
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    if (p[i][j + s] - p[i][j] == s) {
                        sum += s;
                    } else {
                        sum = 0;
                    }
                    mx = max(mx, sum);
                    if (mx >= k) break;
                }
            }
            if (mx >= k) break;
        }
        if (mx >= k) {
            ans = mx;
            l = tm;
        } else {
            r = tm;
        }
    }
    cout << l << ' ' << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...