Submission #1085120

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

burrow

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
stack<int> st;
int a[N][N], cp[N<<1], sz = 0, dp[2][N], fr[N], bk[N], b[N];
signed main(){
	int m, n, k; scanf("%d %d %d", &m, &n, &k);
	for(int i = 0; i<m; ++i) for(int j = 0; j<n; ++j){ scanf("%d", &a[i][j]); cp[sz++] = a[i][j];}
	if(!k){ puts("1000000000"); return 0;}
	sort(cp, cp+sz); sz = unique(cp, cp+sz) - cp;
	int low = 0, high = sz-1;
	pair<int,int> ans = {0, 0};
	while(low <= high){
		int mid = low + ((high-low)>>1), t = cp[mid];
		bool ch = false;
		fill(dp[0], dp[0]+n, 0); fill(dp[1], dp[1]+n, 0);
		for(int i = 0; i<m; ++i){
			int I[2] = {i&1, !(i&1)};
			for(int j = 0; j<n; ++j) b[j] = dp[I[0]][j] = dp[I[1]][j] + (a[i][j] >= t);
			while(!st.empty()) st.pop();
			for(int j = 0; j<n; ++j){
				while(!st.empty() && b[st.top()] >= b[j]) st.pop();
				fr[j] = (!st.empty()) ? st.top() : -1;
				st.push(j);
			}
			while(!st.empty()) st.pop();
			for(int j = n-1; j>=0; --j){
				while(!st.empty() && b[st.top()] >= b[j]) st.pop();
				bk[j] = (!st.empty()) ? st.top() : n;
				st.push(j);
			}
			for(int j = 0; j<n; ++j){ ++fr[j]; --bk[j];}
			for(int j = 0; j<n; ++j){
				int tmp = b[j] * (bk[j] - fr[j] + 1);
				if(tmp >= k){ ans = max(ans, make_pair(t, tmp)); ch = true;}
			}
		}
		if(ch) low = mid+1;
		else high = mid-1;
	}
	printf("%d %d", ans.first, ans.second);
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  int m, n, k; scanf("%d %d %d", &m, &n, &k);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:8:58: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  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