oj.uz

Submission #848611

# Submission time Handle Problem Language Result Execution time Memory
848611 2023-09-13T02:48:32 Z Darren0724 Luxury burrow (IZhO13_burrow) C++17
100 / 100
 459 ms 13912 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int v[N][N]{};
int a[N]{};
int cal(){
    vector<int> st;
    int ans=0;
    for(int i=0;i<N;i++){
        while(st.size()&&a[st.back()]>a[i]){
            int k=a[st.back()];
            st.pop_back();
            int p=(st.size()?st.back()+1:0);
            ans=max(ans,(i-p)*k);
        }
        st.push_back(i);
    }
    return ans;
}
int solve(int m){
    int ans=0;
    for(int j=0;j<N;j++){
        a[j]=0;
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(v[i][j]>=m){
                a[j]++;
            }
            else{
                a[j]=0;
            }
        }
        ans=max(ans,cal());
    }
    return ans;
}
int32_t main() {
    int n,m,k;cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i][j];
        }
    }
    int l=0,r=1e9+5;
    while(r-l>1){
        int mi=(l+r)>>1;
        if(solve(mi)>=k){
            l=mi;
        }
        else{
            r=mi;
        }
    }
    cout<<l<<' '<<solve(l)<<endl;
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 344 KB Output is correct
2 Correct 108 ms 544 KB Output is correct
3 Correct 112 ms 344 KB Output is correct
4 Correct 110 ms 344 KB Output is correct
5 Correct 108 ms 548 KB Output is correct
6 Correct 108 ms 600 KB Output is correct
7 Correct 109 ms 344 KB Output is correct
8 Correct 123 ms 2648 KB Output is correct
9 Correct 113 ms 2648 KB Output is correct
10 Correct 123 ms 2904 KB Output is correct
11 Correct 134 ms 3160 KB Output is correct
12 Correct 116 ms 2648 KB Output is correct
13 Correct 128 ms 2904 KB Output is correct
14 Correct 143 ms 3160 KB Output is correct
15 Correct 150 ms 3404 KB Output is correct
16 Correct 155 ms 3740 KB Output is correct
17 Correct 137 ms 3180 KB Output is correct
18 Correct 221 ms 5456 KB Output is correct
19 Correct 213 ms 4944 KB Output is correct
20 Correct 358 ms 8920 KB Output is correct
21 Correct 355 ms 10324 KB Output is correct
22 Correct 459 ms 13912 KB Output is correct
23 Correct 452 ms 13904 KB Output is correct
24 Correct 263 ms 6988 KB Output is correct
25 Correct 265 ms 6992 KB Output is correct