#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
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")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
428 KB |
Output is correct |
| 5 |
Correct |
1 ms |
432 KB |
Output is correct |
| 6 |
Correct |
1 ms |
552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
304 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
14 ms |
1996 KB |
Output is correct |
| 10 |
Correct |
35 ms |
2176 KB |
Output is correct |
| 11 |
Correct |
73 ms |
2840 KB |
Output is correct |
| 12 |
Correct |
35 ms |
4292 KB |
Output is correct |
| 13 |
Correct |
47 ms |
1452 KB |
Output is correct |
| 14 |
Correct |
105 ms |
4072 KB |
Output is correct |
| 15 |
Correct |
116 ms |
4104 KB |
Output is correct |
| 16 |
Correct |
133 ms |
4480 KB |
Output is correct |
| 17 |
Correct |
112 ms |
4676 KB |
Output is correct |
| 18 |
Correct |
365 ms |
7864 KB |
Output is correct |
| 19 |
Correct |
360 ms |
7628 KB |
Output is correct |
| 20 |
Correct |
730 ms |
12100 KB |
Output is correct |
| 21 |
Correct |
690 ms |
13640 KB |
Output is correct |
| 22 |
Correct |
923 ms |
17756 KB |
Output is correct |
| 23 |
Correct |
916 ms |
17868 KB |
Output is correct |
| 24 |
Correct |
524 ms |
10564 KB |
Output is correct |
| 25 |
Correct |
518 ms |
11024 KB |
Output is correct |
