Submission #315680

#	Time	Username	Problem	Language	Result	Execution time	Memory
315680		Trickster	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1347 ms	26876 KiB

burrow

#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
 
#define N 1010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
 
using namespace std;

int n, m, k;
int v[N][N];
int H[N][N];
pii p[N][N];

int main()
{
	cin >> n >> m >> k;
	
	for(int i = 1; i <= n; i++)
		for(int h = 1; h <= m; h++)
			cin >> v[i][h];
	
	int l = 1, md, r = 1e9, ans, sz;
	while(l <= r) {
		md = (l+r)/2;
		
		char c[N][N];
		for(int i = 1; i <= n; i++)
			for(int h = 1; h <= m; h++) {
				c[i][h] = '0';
				
				if(v[i][h] >= md) c[i][h] = '1';
			}
		
		for(int i = n; i >= 1; i--) {
			memset(H[i], 0, sizeof(H[i]));
			
			for(int h = 1; h <= m; h++) if(c[i][h] == '1') H[i][h] = H[i+1][h] + 1;
		}
		
		for(int i = 1; i <= n; i++) {
			vector <int> E;
			
			for(int h = 1; h <= m; h++) {
				p[i][h] = {0, m};
				
				while(!E.empty() && H[i][E.back()] > H[i][h]) {
					p[i][E.back()].ss = h-1;
					E.pop_back();
				}
				
				if(E.empty()) p[i][h].ff = 1;
				else {
					if(H[i][E.back()] == H[i][h]) p[i][h].ff = p[i][E.back()].ff;
					else p[i][h].ff = E.back()+1;
				}
				
				E.pb(h);
			}
		}
		
		int now = 0;
		for(int i = 1; i <= n; i++)
			for(int h = 1; h <= m; h++)
				now = max(now, H[i][h] * (p[i][h].ss - p[i][h].ff + 1));
		
		if(now >= k) {
			ans = md, sz = now;
			l = md+1;
		} else r = md-1;
	}
	
	cout << ans << " " << sz;
}
/*
3 3 3
1 1 1
1 2 2
1 2 2

1 10 5 
4 3 2 5 10 7 6 5 1 100

3 5 2
5 7 5 5 5
8 5 5 7 5
8 5 8 8 8
*/

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:84:24: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |  cout << ans << " " << sz;
      |                        ^~
burrow.cpp:84:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |  cout << ans << " " << sz;
      |                 ^~~

• Subtask 1: 100 / 100