Submission #1163545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163545		PakinDioxide	호화 벙커 (IZhO13_burrow)	C++17	0 / 100	0 ms	328 KiB

burrow

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    int A[n+1][m+1], l = 0, r = INT_MIN;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> A[i][j], r = max(r, A[i][j]);
    int ans = 0, area = 0;
    while (l <= r) {
        int mid = (l + r)/2;
        // cout << mid << '\n';
        int a[n+1][m+1], mx = 0;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = (A[i][j] < mid ? 1 : 0) + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        tuple <int, int, int> dp[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1] == 1) {dp[i][j] = {0, 0, 0}; /*cout << "0 0 0, ";*/ continue;}
                dp[i][j] = {1, i, j};
                if (i > 1 && get<0>(dp[i-1][j]) > 0 && a[i][j] - a[i][get<2>(dp[i-1][j])-1] - a[i-1][j] + a[i-1][get<2>(dp[i-1][j])-1] == 0 && get<0>(dp[i][j]) < (i-get<1>(dp[i-1][j])+1)*(j-get<2>(dp[i-1][j])+1)) dp[i][j] = {(i-get<1>(dp[i-1][j])+1)*(j-get<2>(dp[i-1][j])+1), get<1>(dp[i-1][j]), get<2>(dp[i-1][j])}; 
                if (j > 1 && get<0>(dp[i][j-1]) > 0 && a[i][j] - a[get<1>(dp[i][j-1])-1][j] - a[i][j-1] + a[get<1>(dp[i][j-1])-1][j-1] == 0 && get<0>(dp[i][j]) < (i-get<1>(dp[i][j-1])+1)*(j-get<2>(dp[i][j-1])+1)) dp[i][j] = {(i-get<1>(dp[i][j-1])+1)*(j-get<2>(dp[i][j-1])+1), get<1>(dp[i][j-1]), get<2>(dp[i][j-1])};
                mx = max(mx, get<0>(dp[i][j]));
                // cout << get<0>(dp[i][j]) << ' ' << get<1>(dp[i][j]) << ' ' << get<2>(dp[i][j]) << ", ";
            }
            // cout << '\n';
        }
        if (mx < k) r = mid-1;
        else ans = mid, l = mid+1, area = mx;
        // cout << "MX " << mx << '\n';
    }
    cout << ans << ' ' << area << '\n';
}

• Subtask 1: 0 / 100