Submission #690431

#	Time	Username	Problem	Language	Result	Execution time	Memory
690431		moonhero	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	605 ms	21840 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];

int c (int dp[]) {
    int i = 0, ar = 0, ans = 0;
    stack <int> st;
    while (i < m) {
        if (st.size() == 0 || dp[st.top() + 1] <= dp[i + 1]) st.push(i++);
        else {
            int tp = dp[st.top() + 1];
            st.pop();
            ar = tp * i;
            if (st.size()) ar = tp * (i - st.top() - 1);
            ans = max(ans, ar);
            // cout << ar << ' ' << i << '\n';
        }
    } 
    while (st.size()) {
        int tp = dp[st.top() + 1];
        st.pop();
        ar = tp * i;
        if (st.size()) ar = tp * (i - st.top() - 1);
        ans = max(ans, ar);
        // cout << ar << ' ' << i << '\n';
    } return ans;
}

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 = c(x[1]);
    // cout << ans << ' ';
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (x[i][j]) x[i][j] += x[i - 1][j];
        }
        ans = max(ans, c(x[i]));
        // cout << ans << ' ';
    } 
    // cout << '\n';
    if (ans >= nd) return ans;
    else return 0;
}

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