Submission #42319

#	Time	Username	Problem	Language	Result	Execution time	Memory
42319		wzy	Luxury burrow (IZhO13_burrow)	C++11	100 / 100	698 ms	16544 KiB

burrow

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
#define int long long
int n , m , k;
int v[1005][1005] , h[1005][1005];



int get(vector<int> v){
	int n = v.size();
	int ansj = -1;
	stack<int> s;
	for(int i = 0 ; i <n;i++){
		while(s.size() && v[s.top()] >= v[i] ){
			int left;
			int u = s.top();
			s.pop();
			if(s.size()) left = s.top() + 1;
			else left = 0;
			int right = i - 1;
			ansj = max(ansj , (right - left + 1)*v[u]);
		}
		s.push(i);
	}
	while(s.size()){
		int u = s.top();
		s.pop();
		int left;
		if(s.size()) left = s.top() + 1;
		else left = 0;
		int right = n - 1;
		ansj = max(ansj , (right - left + 1)*v[u]);
	}
	return ansj;
}


int32_t main(){
	scanf("%lld%lld%lld" , &n , &m  ,&k);
	for(int i = 0 ; i<n;i++){
		for(int j = 0 ; j < m;j++)scanf("%lld" , &v[i][j]);
	}
	int l = 0 , r =(int) 1e9;
	int ansj = -1 , maxansjii;
	while(l<=r){
		int mid = (l+r)/2;
		for(int i = 0 ; i < n;i++){
			for(int j = 0 ; j <m ;j++){
				if(i){
					if(v[i][j] >= mid) h[i][j] = 1 + h[i-1][j];
					else h[i][j] = 0;
				}
				else{
					if(v[i][j] >= mid) h[i][j] = 1;
					else h[i][j] = 0;
				}
			}
		}
		int currarr = -1;
		for(int i = 0 ; i < n;i++){
			vector<int> t;
			for(int j = 0 ; j < m ; j++) t.pb(h[i][j]);
			currarr = max(currarr , get(t));
		}
		if(currarr >= k){
			ansj = max(ansj , mid);
			maxansjii = currarr;
			l = mid + 1;			
		}
		else r = mid - 1;
	}
	cout<<ansj<<" "<<maxansjii<<endl;
}

Compilation message (stderr)

burrow.cpp: In function 'int32_t main()':
burrow.cpp:43:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld" , &n , &m  ,&k);
                                      ^
burrow.cpp:45:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int j = 0 ; j < m;j++)scanf("%lld" , &v[i][j]);
                                                     ^

• Subtask 1: 100 / 100