Submission #359351

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
359351	2021-01-26T23:35:25 Z	aZvezda	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	990 ms	25924 KB

burrow

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const ll MAX_N = 1e3 + 10;
ll tab[MAX_N][MAX_N];
ll k;
ll n, m;
ll howm[MAX_N][MAX_N];
ll l[MAX_N], r[MAX_N];

ll eval(ll x) {
    for(ll j = 0; j < m; j ++) {
        howm[0][j] = tab[0][j] >= x;
    }
    for(ll i = 1; i < n; i ++) {
        for(ll j = 0; j < m; j ++) {
            if(tab[i][j] >= x) {
                howm[i][j] = howm[i - 1][j] + 1;
            } else {
                howm[i][j] = 0;
            }
        }
    }
    ll mx = 0;
    for(ll i = 0; i < n; i ++) {
        stack<ll> st;
        for(ll j = 0; j < m; j ++) {
            while(!st.empty() && howm[i][st.top()] >= howm[i][j]) {
                st.pop();
            }
            if(st.empty()) {
                l[j] = 0;
            } else {
                l[j] = st.top() + 1;
            }
            st.push(j);
        }
        while(!st.empty()) {st.pop();}
        for(ll j = m - 1; j >= 0; j --) {
            while(!st.empty() && howm[i][st.top()] >= howm[i][j]) {
                st.pop();
            }
            if(st.empty()) {
                r[j] = m - 1;
            } else {
                r[j] = st.top() - 1;
            }
            st.push(j);
        }
        while(!st.empty()) {st.pop();}
        for(ll j = 0; j < m; j ++) {
            chkmax(mx, howm[i][j] * (r[j] - l[j] + 1));
        }
    }
    return mx;
}

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> k;
    for(ll i = 0; i < n; i ++) {
        for(ll j = 0; j < m; j ++) {
            cin >> tab[i][j];
        }
    }
    ll l = 0, r = mod;
    while(l < r - 1) {
        ll m = (l + r) / 2ll;
        if(eval(m) >= k) {
            l = m;
        } else {
            r = m;
        }
    }
    cout << l << " " << eval(l) << endl;
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	8 ms	1260 KB	Output is correct
9	Correct	16 ms	2284 KB	Output is correct
10	Correct	41 ms	2924 KB	Output is correct
11	Correct	78 ms	3948 KB	Output is correct
12	Correct	38 ms	5228 KB	Output is correct
13	Correct	52 ms	2412 KB	Output is correct
14	Correct	118 ms	6636 KB	Output is correct
15	Correct	127 ms	6692 KB	Output is correct
16	Correct	152 ms	7148 KB	Output is correct
17	Correct	136 ms	8832 KB	Output is correct
18	Correct	397 ms	12696 KB	Output is correct
19	Correct	384 ms	13292 KB	Output is correct
20	Correct	800 ms	18540 KB	Output is correct
21	Correct	742 ms	20880 KB	Output is correct
22	Correct	954 ms	25872 KB	Output is correct
23	Correct	990 ms	25924 KB	Output is correct
24	Correct	587 ms	18540 KB	Output is correct
25	Correct	591 ms	19052 KB	Output is correct