Submission #42318

# Submission time Handle Problem Language Result Execution time Memory
42318 2018-02-26T01:31:47 Z wzy Luxury burrow (IZhO13_burrow) C++11
0 / 100
2 ms 376 KB
#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> t){
	int ansj = 0;
	stack<int> s;
	for(int i = 0 ; i <t.size();i++){
		while(s.size() && t[s.top()] >= t[i]){
			int lefti = 0;
			int u = s.top();
			s.pop();
			if(s.size()) lefti = s.top();
			ansj  = max(ansj , (u - lefti)*(t[u]));
		}
		s.push(i);
	}
	while(!s.empty()){
		int u = s.top();
		int leftii = 0;
		s.pop();
		if(s.size())leftii = s.top();
		ansj = max(ansj , ((u)  - (leftii))*(t[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

burrow.cpp: In function 'long long int get(std::vector<long long int>)':
burrow.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i <t.size();i++){
                    ^
burrow.cpp: In function 'int32_t main()':
burrow.cpp:36: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:38: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]);
                                                     ^
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -