oj.uz

Submission #1010756

# Submission time Handle Problem Language Result Execution time Memory
1010756 2024-06-29T10:33:02 Z bornag Luxury burrow (IZhO13_burrow) C++14
0 / 100
 75 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 348 KB Output is correct
2 Incorrect 75 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -