Submission #690294

#	Time	Username	Problem	Language	Result	Execution time	Memory
690294		moonhero	Luxury burrow (IZhO13_burrow)	C++14	0 / 100	1889 ms	12476 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, nd, 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) {
    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];
        } 
    } 
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = i; k <= n; k++) {
                int l = j, r = m, res = 0;
                while (l <= r) {
                    int md = (l + r) / 2;
                    int ar = (md - j + 1) * (k - i + 1);
                    int sum = ps[k][md] - ps[i - 1][md] - ps[k][j - 1] + ps[i - 1][j - 1];
                    if (sum == ar) l = md + 1, res = md;
                    else r = md - 1;
                } 
                res = (res - j + 1) * (k - i + 1);
                if (res >= nd) {
                    ans = max(ans, res);
                }
            }
        }
    } return ans;
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> nd;
    if (n > 200 || m > 200) abort();
    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