Submission #400486

#	Time	Username	Problem	Language	Result	Execution time	Memory
400486		Lawliet	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	515 ms	13988 KiB

burrow

#include <bits/stdc++.h>
 
#define MAX 1010
#define INF 1000000010
 
using namespace std;
 
int n, m, k;
 
int L[MAX];
int R[MAX];
int v[MAX][MAX];
int histogram[MAX];
 
int largestRectangle()
{
	for(int g = 1 ; g <= m ; g++)
	{
		int cur = g - 1;
 
		while(histogram[g] <= histogram[cur]) cur = L[cur];
 
		L[g] = cur;
	}
 
	for(int g = m ; g >= 1 ; g--)
	{
		int cur = g + 1;
 
		while(histogram[g] <= histogram[cur]) cur = R[cur];
 
		R[g] = cur;
	}
 
	int ans = 0;
 
	for(int g = 1 ; g <= m ; g++)
		ans = max(ans , histogram[g]*(R[g] - L[g] - 1));
 
	return ans;
}
 
bool test(int l, int t = 0)
{
	int ans = -1;
 
	memset(histogram , 0 , sizeof(histogram));
	histogram[0] = histogram[m + 1] = -INF;
 
	for(int g = 1 ; g <= n ; g++)
	{
		for(int h = 1 ; h <= m ; h++)
		{
			if(v[g][h] >= l) histogram[h]++;
			else histogram[h] = 0;
		}
 
		ans = max(ans , largestRectangle());
	}
 
	if(t == 1) printf("%d\n",ans);
 
	return ans >= k;
}
 
int bs()
{
	int l = 0, r = INF;
 
	while(l < r)
	{
		int m = (l + r)/2;
		if( l == r - 1 ) m = r;
 
		if( test(m) ) l = m;
		else r = m - 1;
	}
 
	return l;
}
 
void init()
{
	L[0] = 0;
	R[m + 1] = m + 1;
}
 
int main()
{
	scanf("%d %d %d",&n,&m,&k);
 
	init();
 
	for(int g = 1 ; g <= n ; g++)
		for(int h = 1 ; h <= m ; h++)
			scanf("%d",&v[g][h]);
 
	int ans = bs();
 
	printf("%d ",ans);
 
	test(ans , 1);
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d %d %d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
burrow.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |    scanf("%d",&v[g][h]);
      |    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100