Submission #524533

#	Time	Username	Problem	Language	Result	Execution time	Memory
524533		ezdp	Luxury burrow (IZhO13_burrow)	C++14	0 / 100	1 ms	288 KiB

burrow

#pragma GCC target ("sse4")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define lsb(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are less than x
/// insert(x)		 -> inserts x into the set

const int MAXN = 1e3 + 3;

int n, m, k, A[MAXN][MAXN], dp[MAXN][MAXN], l[MAXN], r[MAXN];

ll eval(int x, int DEBUG = 0){
	ll ans = 0;
	for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++){
		dp[i][j] = (A[i][j] >= x ? 1 : 0);
	}
	for(int i = 1; i < n; i ++) for(int j = 0; j < m; j ++){
		if(dp[i][j]) dp[i][j] += dp[i - 1][j];
	}
	for(int i = 0; i < n; i ++){
		if(DEBUG) de(i);
		if(DEBUG){ for(int j = 0; j < m; j ++) cout << dp[i][j] << " "; cout << endl; }
		stack<int> st;
		for(int j = 0; j < m; j ++){
			while(!st.empty() && dp[i][st.top()] >= dp[i][j]){
				st.pop();
			}
			if(!st.empty()){
				l[j] = st.top();
			}
			st.push(j);
		}
		while(!st.empty()) st.pop();
		for(int j = m - 1; j >= 0; j --){
			while(!st.empty() && dp[i][st.top()] >= dp[i][j]){
				st.pop();
			}
			if(!st.empty()){
				r[j] = st.top();
			}
			else{
				r[j] = m;
			}
			st.push(j);
		}
		if(DEBUG) for(int j = 0; j < m; j ++) cout << dp[i][j] << " " << l[j] << " " << r[j] << endl;
		for(int j = 0; j < m; j ++){
			ans = max(ans, 1LL * dp[i][j] * (r[j] - l[j] - 1));
		}
	}	
	return ans;
}

int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	/// freopen("filename.in" , "r", stdin); 
	/// freopen("filename.out", "w", stdout);
	cin >> n >> m >> k;
	for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++){
		cin >> A[i][j];
	}
	int l = 1, r = 1e9, ans = 1;
	while(l <= r){
		int m = (l + r) / 2;
		if(eval(m) >= k){
			l = m + 1;
			ans = m;
		}
		else{
			r = m - 1;
		}
	}
	cout << ans << " " << eval(ans) << endl;
	
}
/**
3 3 3
1 1 1
1 2 2
1 2 2
2 4

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

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

Compilation message (stderr)

burrow.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
burrow.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 0 / 100