oj.uz

Submission #690294

# Submission time Handle Problem Language Result Execution time Memory
690294 2023-01-30T05:48:35 Z moonhero Luxury burrow (IZhO13_burrow) C++14
0 / 100
 1889 ms 12476 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 7 ms 12064 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 9 ms 12180 KB Output is correct
6 Correct 9 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 70 ms 12116 KB Output is correct
9 Correct 647 ms 12280 KB Output is correct
10 Correct 1889 ms 12476 KB Output is correct
11 Runtime error 1 ms 468 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -