Submission #1085106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085106		Sunbae	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	0 ms	356 KiB

burrow

#include <cstdio>
#include <algorithm>
const int N = 1005;
int m, n, k, a[N][N], cp[N<<1], up[N][N], fr[N], bk[N], st[N], sz;
signed main(){
	scanf("%d %d %d", &m, &n, &k); sz = 0;
	for(int i = 0; i<m; ++i) for(int j = 0; j<n; ++j) scanf("%d", &a[i][j]), cp[sz++] = a[i][j];
	std::sort(cp, cp+sz); sz = std::unique(cp, cp+sz) - cp;	
	int low = 0, high = sz-1;
	std::pair<int,int> ans;
	while(low <= high){
		int mid = low + ((high-low)>>1), t = cp[mid], mx = 0;
		for(int i = 0; i<m; ++i){	
			for(int j = 0; j<n; ++j) up[i][j] = (i ? up[i-1][j] : 0) + (a[i][j] >= t);
			sz = 0;
			for(int j = 0; j<n; ++j){
				while(sz > 0 && up[i][st[sz-1]] >= up[i][j]) --sz;
				fr[j] = sz ? st[sz-1] : -1;
				st[sz++] = j;
			}	
			sz = 0;
			for(int j = n-1; j>=0; --j){
				while(sz > 0 && up[i][st[sz-1]] >= up[i][j]) --sz;
				bk[j] = sz ? st[sz-1] : n;			
				st[sz++] = j;
			}
			for(int j = 0; j<n; ++j) ++fr[j], --bk[j];
			for(int j = 0; j<n; ++j) if(up[i][j] * (bk[j] - fr[j] + 1) >= k) mx = std::max(mx, up[i][j] * (bk[j] - fr[j] + 1)); 
		}
		if(mx) low = mid+1, ans = std::make_pair(t, mx);
		else high = mid-1;
	}
	printf("%d %d", ans.first, ans.second);
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:6:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |  scanf("%d %d %d", &m, &n, &k); sz = 0;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:7:57: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  for(int i = 0; i<m; ++i) for(int j = 0; j<n; ++j) scanf("%d", &a[i][j]), cp[sz++] = a[i][j];
      |                                                    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100