Submission #683089

#	Time	Username	Problem	Language	Result	Execution time	Memory
683089		Ronin13	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	876 ms	17844 KiB

burrow

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1001;
int a[nmax][nmax];
int last[nmax][nmax];
int n, m;
int k;
int ans = 0;
bool check(int X){
    int mx = -1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] >= X)
                last[i][j] = last[i - 1][j] + 1;
            else last[i][j] = 0;
        }

        stack <int> st;
        vector <int> dr(m + 1), dl(m + 1);
        for(int j = 1; j <= m; j++){
            while(!st.empty()){
                int v = st.top();
                if(last[i][v] >= last[i][j])
                    st.pop();
                else break;
            }
            if(st.empty()) dl[j] = 0;
            else dl[j] = st.top();
            st.push(j);
        }
        while(!st.empty())
            st.pop();
        for(int j = m; j >= 1; j--){
            while(!st.empty()){
                int v = st.top();
                if(last[i][v] >= last[i][j])
                    st.pop();
                else break;
            }
            if(st.empty()) dr[j] = m + 1;
            else dr[j] = st.top();
            st.push(j);
        }
        for(int j = 1; j <= m; j++){
            //cout << dr[j] << ' ' << dl[j] << "\n";
            mx = max(mx, (dr[j] - dl[j] - 1) * last[i][j]);
        }
    }
    if(mx >= k) {
        ans = mx;
        return true;
    }
    return false;
}

int main(){
  //  freopen("school.in", "r", stdin);
 // freopen("school.out", "w", stdout);
    cin >> n >> m;
    cin >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];
    }
    int l = 0, r = 1e9 + 1;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l << ' ' << ans << "\n";
    return 0;
}

• Subtask 1: 100 / 100