Submission #389567

#	Time	Username	Problem	Language	Result	Execution time	Memory
389567		knightron0	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	519 ms	23372 KiB

burrow

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e3 + 5;

int n, m, k;
int a[MAXN][MAXN], val[MAXN][MAXN];

int max_area(vector<int> vec){
    stack<int> s;
    int ans = 0;
    int i = 0;
    while(i < m){
        if(s.empty()){ 
            s.push(i);
        } else {
            if(vec[s.top()] > vec[i]){
                int h = vec[s.top()];
                s.pop();
                int res;
                if(s.empty()){
                    res = h * i;
                } else {
                    res = h * (i-(s.top() +1));
                }
                ans = max(ans, res);
                continue;
            } else {
                s.push(i);
            }
        }
        i++;
    }
    while(!s.empty()){
        int h = vec[s.top()];
        s.pop();
        int res;
        if(s.empty()){
            res = h * i;
        } else {
            res = h * (i-(s.top() +1));
        }
        ans = max(ans, res);
    }
    return ans;
}


int check(int x){
    for(int i= 0;i<n;i++){
        for(int j= 0;j<m;j++){
            if(a[i][j] >= x){
                val[i][j] = 1;
            } else {
                val[i][j]= 0;
            }
        }
    }
    vector<int> v;
    for(int i=0;i<m;i++){
        v.pb(val[0][i]);
    }
    int ans = max_area(v);
    for(int i= 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(val[i][j] && i > 0){
                val[i][j] += val[i - 1][j];
            }
        }
        v.clear();
        for(int j=0;j<m;j++){
            v.pb(val[i][j]);
        }
        ans = max(ans, max_area(v));
    }
    return ans;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    cin>>n>>m>>k;
    for(int i= 0;i<n;i++){
        for(int j= 0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int lo =0;
    int ans= 0;
    int hi = 1e9;
    while(lo < hi){
        int m = (lo + hi)/2;
        int sz = check(m);
        if(sz >= k){
            lo = m+1;
            ans = max(ans, m);
        } else {
            hi = m-1;
        }
    }
    if(check(lo) >= k) ans = max(lo, ans);
    if(check(hi) >= k) ans = max(hi, ans);
    cout<<ans<<' '<<check(ans)<<endl;
    return 0;
}

• Subtask 1: 100 / 100