oj.uz

Submission #122602

# Submission time Handle Problem Language Result Execution time Memory
122602 2019-06-28T17:50:52 Z Lawliet Luxury burrow (IZhO13_burrow) C++14
0 / 100
 34 ms 1280 KB 
#include <bits/stdc++.h>

#define MAX 410
#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

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]
  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]
    scanf("%d",&v[g][h]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 8 ms 768 KB Output is correct
10 Correct 22 ms 1024 KB Output is correct
11 Correct 34 ms 1280 KB Output is correct
12 Incorrect 8 ms 1144 KB Output isn't correct
13 Halted 0 ms 0 KB -