제출 #690064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
690064		moonhero	호화 벙커 (IZhO13_burrow)	C++14	0 / 100	2089 ms	12168 KiB

burrow

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3 + 5;
int a[N][N], x[N][N], n, m, k, ps[N][N];

bool c (int ar, int l, int r) {
    // cout << ar << '\n';
    for (int i = 1; i <= sqrt(ar); i++) {
            int k = l + i - 1, j = r + (ar / i) - 1;
        if (k <= n && j <= m) {
            int sum = ps[k][j] - ps[l - 1][j] - ps[k][r - 1] + ps[l - 1][r - 1];
            // cout << l << ' ' << r << ' ' << k << ' ' << j << ' ' << sum << '\n';
            if (sum == ar) return 1;
        }
    } for (int i = 1; i <= sqrt(ar); i++) {
        int k = l + (ar / i) - 1, j = r + i - 1;
        if (k <= n && j <= m) {
            int sum = ps[k][j] - ps[l - 1][j] - ps[k][r - 1] + ps[l - 1][r - 1];
            // cout << l << ' ' << r << ' ' << k << ' ' << j << ' ' << sum << '\n';
            if (sum == ar) return 1;
        }
    } return 0;
}

int check (int d) {
    // cout << d << '\n';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] >= d) x[i][j] = 1;
            else x[i][j] = 0;
            ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + x[i][j];
            // cout << ps[i][j] << ' ';
        } 
        // cout << '\n';
    } 
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int l = k, r = (n - i + 1) * (m - j + 1), res = 0;
            for (int ar = l; ar <= r; ar++) {
                // int md = (l + r) / 2;
                // // cout << md << ' ' << c(md, i, j) << '\n';
                // if (c(md, i, j)) l = md + 1, res = md;
                // else r = md - 1;
                if (c(ar, i, j)) res = ar;
            } 
            ans = max(ans, res);
        }
    } return ans;
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    int mx = 0;
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < N; j++) 
            a[i][j] = 0, x[i][j] = 0, ps[i][j] = 0;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
        }
    int l = 0, r = mx, res = 0, ans = 0;
    while (l <= r) {
        int md = (l + r) / 2;    
        // cout << md << '\n';  
        if (check(md) > 0) l = md + 1, res = md, ans = check(md);
        else r = md - 1;
    } cout << res << ' ' << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 100