Submission #995658

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
995658	2024-06-09T15:47:42 Z	LOLOLO	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	1114 ms	65536 KB

burrow

#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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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