#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
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 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
