Submission #1010756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010756		bornag	Luxury burrow (IZhO13_burrow)	C++14	0 / 100	75 ms	348 KiB

burrow

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

const int maxn = 1007;

#define ll long long

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

ll heights[maxn];
 
ll prv[maxn];
ll nxt[maxn];

ll pov = -1;

ll calc(){
	
    ll sol = -1;
    
    for(int i = 0; i < m; i++){
    	ll lf = i; ll rt = i;
    	
    	while(heights[lf] >= heights[i]){
    		lf--;
		}
		
		while(heights[rt] >= heights[i]){
			rt++;
		}
		
		sol = max(sol, (rt-lf-1)*heights[i]);
	}
 
    return sol;
}

bool check(ll height){
	
	pov = -1;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			
			if(plot[i][j] >= height){
				heights[j]++;
			} else {
				heights[j] = 0;
			}
			
		}
		
		pov = max(pov, calc());
	}
	
	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(int i = 0; i < n; i++){
		for(int 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;
		
		if(check(mid)){
			lo = mid+1;
		} else {
			hi = mid-1;
		}
	}
 	
 	check(hi);
 
    cout << hi << ' ' << pov << endl;
}

• Subtask 1: 0 / 100