oj.uz

Submission #340433

# Submission time Handle Problem Language Result Execution time Memory
340433 2020-12-27T15:29:39 Z amunduzbaev Luxury burrow (IZhO13_burrow) C++14
100 / 100
 1198 ms 18036 KB 
/** made by amunduzbaev **/
 
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const int N = 1e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, t, a[N][N];
int tmp[N][N];
int check(int mx){
	memset(tmp, 0, sizeof tmp);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j] >= mx) tmp[i][j] = 1;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(tmp[i][j] && i) tmp[i][j] += tmp[i-1][j];
		}
	}
	int ans = 0;
	for(int i=0;i<n;i++){
		stack<pii> ss;
		vii l(m), r(m);
		
		for(int j=0;j<m;j++){
			if(tmp[i][j] == 0){
				while(!ss.empty()) ss.pop();
				continue;
			}
			int in = j;
			while(!ss.empty() && ss.top().ff >= tmp[i][j]) {in = ss.top().ss; ss.pop(); }
			
			l[j] = j - in+1;
			
			ss.push({tmp[i][j], in});
		}
		
		while(!ss.empty()) ss.pop();
		for(int j=m-1;j>=0;j--){
			if(tmp[i][j] == 0){
				while(!ss.empty()) ss.pop();
				continue;
			}
			
			int in = j;
			while(!ss.empty() && ss.top().ff >= tmp[i][j]) {in = ss.top().ss; ss.pop(); }
			
			r[j] = in - j+1;
			
			ss.push({tmp[i][j], in});
		}
		for(int j=0;j<m;j++) umax(ans, (r[j] + l[j] -1)*tmp[i][j]);
		
	}
	
	return ans;
}
 
void solve(){
	cin>>n>>m>>k;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) cin>>a[i][j];
	int l = 1, r = mod;
	while(l+1 < r){
		int m = (l + r) >>1;
		if(check(m) >= k) l = m;
		else r = m-1;
	}
	if(check(r) >= k) l = r;
	cout<<l<<" "<<check(l);
	return;
}
 
int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4332 KB Output is correct
2 Correct 9 ms 4332 KB Output is correct
3 Correct 8 ms 4332 KB Output is correct
4 Correct 9 ms 4464 KB Output is correct
5 Correct 10 ms 4480 KB Output is correct
6 Correct 8 ms 4480 KB Output is correct
7 Correct 9 ms 4460 KB Output is correct
8 Correct 14 ms 4716 KB Output is correct
9 Correct 24 ms 5228 KB Output is correct
10 Correct 42 ms 5356 KB Output is correct
11 Correct 99 ms 5868 KB Output is correct
12 Correct 44 ms 6380 KB Output is correct
13 Correct 50 ms 5100 KB Output is correct
14 Correct 117 ms 6636 KB Output is correct
15 Correct 122 ms 6508 KB Output is correct
16 Correct 166 ms 6892 KB Output is correct
17 Correct 114 ms 6764 KB Output is correct
18 Correct 401 ms 9452 KB Output is correct
19 Correct 362 ms 9068 KB Output is correct
20 Correct 856 ms 13036 KB Output is correct
21 Correct 845 ms 14184 KB Output is correct
22 Correct 1198 ms 18036 KB Output is correct
23 Correct 1163 ms 18028 KB Output is correct
24 Correct 527 ms 10988 KB Output is correct
25 Correct 464 ms 11116 KB Output is correct