oj.uz

Submission #47579

# Submission time Handle Problem Language Result Execution time Memory
47579 2018-05-05T05:45:14 Z dqhungdl Luxury burrow (IZhO13_burrow) C++17
100 / 100
 569 ms 4732 KB 
#include <bits/stdc++.h>
using namespace std;

int m,n,k,L[1005],R[1005],h[1005],a[1005][1005];

int Check(int lim)
{
	for(int i=1;i<=n;i++)
		h[i]=0;
	int maxn=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
			if(a[i][j]>=lim)
				h[j]++;
			else
				h[j]=0;
		for(int j=1;j<=n;j++)
	    {
	    	L[j]=j;
	        int tmp=j-1;
	        while(tmp>0&&h[j]<=h[tmp])
	        {
	            L[j]=L[tmp];
	            tmp=L[tmp]-1;
	        }
	    }
	    for(int j=n;j>=1;j--)
	    {
	        R[j]=j;
	        int tmp=j+1;
	        while(tmp<=n&&h[j]<=h[tmp])
	        {
	            R[j]=R[tmp];
	            tmp=R[tmp]+1;
	        }
	    }
	    for(int j=1;j<=n;j++)
	    	maxn=max(maxn,h[j]*(R[j]-L[j]+1));		   
	}
	return maxn;
}

int main()
{
	ios_base::sync_with_stdio(false);
	//freopen("TEST.INP","r",stdin);
	//freopen("TEST.OUT","w",stdout);
	cin>>m>>n>>k;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	int area,rs,l=1,r=1e9;
	while(l<=r)
	{
		int mid=(l+r)/2;
		int tmp=Check(mid);
		if(tmp>=k)
		{
			area=tmp;
			rs=mid;
			l=mid+1;
		}
		else
			r=mid-1;
	}
	cout<<rs<<' '<<area;
}

Compilation message

burrow.cpp: In function 'int main()':
burrow.cpp:67:12: warning: 'rs' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout<<rs<<' '<<area;
            ^~~
burrow.cpp:67:15: warning: 'area' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout<<rs<<' '<<area;
  ~~~~~~~~~~~~~^~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 6 ms 972 KB Output is correct
9 Correct 9 ms 1360 KB Output is correct
10 Correct 24 ms 1488 KB Output is correct
11 Correct 48 ms 1640 KB Output is correct
12 Correct 22 ms 2556 KB Output is correct
13 Correct 31 ms 2556 KB Output is correct
14 Correct 69 ms 2556 KB Output is correct
15 Correct 71 ms 2556 KB Output is correct
16 Correct 85 ms 2556 KB Output is correct
17 Correct 73 ms 2636 KB Output is correct
18 Correct 219 ms 2940 KB Output is correct
19 Correct 224 ms 3368 KB Output is correct
20 Correct 487 ms 3836 KB Output is correct
21 Correct 427 ms 4220 KB Output is correct
22 Correct 530 ms 4732 KB Output is correct
23 Correct 569 ms 4732 KB Output is correct
24 Correct 378 ms 4732 KB Output is correct
25 Correct 342 ms 4732 KB Output is correct