Submission #1010773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010773		bornag	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	422 ms	17920 KiB

burrow

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

const int maxn = 1007;

#define ll long long

ll n, m, k;
ll plot[maxn][maxn]; 

ll heights[maxn];
 
ll lft[maxn];
ll rt[maxn];

ll pov = -1;

ll calc(){
	
    stack<ll> prije;
 
    for (ll i = 0; i < m; i++) {
    	
        while (!prije.empty() && heights[prije.top()] >= heights[i]) {
            prije.pop();
        }
 
        if (!prije.empty()) {
            lft[i] = prije.top();
        }
        else {
            lft[i] = -1;
        }
 
        prije.push(i);
    }
 
    stack<ll> poslije;
 
    for (ll i = m-1; i >= 0; i--) {
    	
        while (!poslije.empty() && heights[poslije.top()] >= heights[i]) {
            poslije.pop();
        }
 
        if (!poslije.empty()) {
            rt[i] = poslije.top();
        } else {
            rt[i] = m;
        }
 
        poslije.push(i);
    }
 
    ll sol = 0;
 
    for (ll i = 0; i < m; i++)
    {
        sol = max(sol, heights[i] * (rt[i] - lft[i] - 1));
    }
 
    return sol;
}

bool check(ll height){
	
	for (int i = 0; i < m; i++) {
        heights[i] = 0;
    }
	
	pov = -1;
	
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < m; j++){
			
			if(plot[i][j] >= height){
				heights[j]++;
			} else {
				heights[j] = 0;
			}
			
		}
		
		ll r = calc();
		pov = max(pov, r);
	}
	
	return pov >= k;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> k;
	
	ll mxv = -1;
	ll mv = LLONG_MAX;
	
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < m; j++){
			cin >> plot[i][j];
			
			mxv = max(plot[i][j], mxv);
			mv = min(plot[i][j], mv);
		}
	}
	
	ll lo = mv;
	ll hi = mxv;
	
	while(lo < hi){
		ll mid = (lo+hi)/2+1;
		
		if(check(mid)){
			lo = mid;
		} else {
			hi = mid-1;
		}
	}
 	
 	check(lo);
 
    cout << lo << ' ' << pov << endl;
}

• Subtask 1: 100 / 100