Submission #524556

#	Time	Username	Problem	Language	Result	Execution time	Memory
524556		ezdp	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	923 ms	17868 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];

int eval(int x){
	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] + 1;
	}
	int ret = 0;
	for(int i = 0; i < n; i ++){
		stack<int> st;
		for(int j = 0; j < m; j ++){
			while(!st.empty() && dp[i][st.top()] >= dp[i][j]){
				st.pop();
			}
			L[j] = (st.empty() ? 0 : st.top() + 1);
			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();
			}
			R[j] = (st.empty() ? m - 1 : st.top() - 1);
			st.push(j);
		}
		for(int j = 0; j < m; j ++){
			ret = max(ret, dp[i][j] * (R[j] - L[j] + 1));
		}
	}
	return ret;
}

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 = 0, r = 1e9;
	while(l < r - 1){
		int m = (l + r) / 2;
		if(eval(m) >= k) l = m;
		else			 r = m;
	}
	cout << l << " " << eval(l) << 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: 100 / 100