답안 #995658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
995658 2024-06-09T15:47:42 Z LOLOLO 호화 벙커 (IZhO13_burrow) C++17
100 / 100
1114 ms 65536 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e3 + 10;
int n, m, k;
int is[N][N], pr[N], l[N], r[N];

int area() {
    stack <int> st;
    for (int i = 1; i <= m; i++) {
        while (sz(st) && pr[i] < pr[st.top()]) {
            st.pop();
        }

        l[i] = sz(st) ? st.top() : 0;
        st.push(i);
    }

    while (sz(st))
        st.pop();

    int ans = 0;
    for (int i = m; i >= 1; i--) {
        while (sz(st) && pr[i] <= pr[st.top()])
            st.pop();

        r[i] = sz(st) ? st.top() : m + 1;
        ans = max(ans, (r[i] - l[i] - 1) * pr[i]);
        st.push(i);
    }

    return ans;
}

int check() {
    mem(pr, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (is[i][j]) {
                pr[j]++;
            } else {
                pr[j] = 0;
            }
        }

        ans = max(ans, area());
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    vector < vector <int>> cell;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            cell.pb({x, i, j});
        }
    }

    sort(all(cell), greater <vector <int>>() );
    int l = 0, r = 1e9, m, ans = 0, area = 0;

    while (l <= r) {
        m = (l + r) / 2;
        mem(is, 0);
        for (int j = 0; j < sz(cell); j++) {
            if (cell[j][0] >= m) {
                is[cell[j][1]][cell[j][2]] = 1;
            } else {
                break;
            }
        }

        int v = check();
        if (v >= k) {
            ans = m;
            area = v;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    cout << ans << " " << area << '\n';

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 4 ms 4444 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 5 ms 4440 KB Output is correct
7 Correct 4 ms 4444 KB Output is correct
8 Correct 9 ms 5016 KB Output is correct
9 Correct 14 ms 5540 KB Output is correct
10 Correct 32 ms 6928 KB Output is correct
11 Correct 50 ms 8392 KB Output is correct
12 Correct 33 ms 7180 KB Output is correct
13 Correct 39 ms 7456 KB Output is correct
14 Correct 101 ms 14328 KB Output is correct
15 Correct 100 ms 13812 KB Output is correct
16 Correct 103 ms 15364 KB Output is correct
17 Correct 142 ms 18420 KB Output is correct
18 Correct 270 ms 27120 KB Output is correct
19 Correct 329 ms 33092 KB Output is correct
20 Correct 673 ms 47592 KB Output is correct
21 Correct 779 ms 56624 KB Output is correct
22 Correct 1081 ms 65536 KB Output is correct
23 Correct 1114 ms 65536 KB Output is correct
24 Correct 598 ms 49640 KB Output is correct
25 Correct 659 ms 62800 KB Output is correct