Submission #49778

#	Time	Username	Problem	Language	Result	Execution time	Memory
49778		mra2322001	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1141 ms	62528 KiB

burrow

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)

using namespace std;
typedef long long ll;
const int N = 1002;

int m, n, a[N][N], d[N][N], b[N], l[N], r[N], arr[N][N], k;
vector <int> save;

int check(int x){
    f1(i, m) f1(j, n){
        d[i][j] = 0;
        if(arr[i][j] >= x) a[i][j] = 1;
        else a[i][j] = 0;
    }
    f1(i, m){
        for(int j = n; j>= 1; j--){
            if(!a[i][j]) d[i][j] = 0;
            else{
                d[i][j] = d[i][j + 1] + 1;
            }
         }
    }
    int res = 0;
    f1(j, n){
        f1(i, m) b[i] = d[i][j], l[i] = r[i] = 0;
        stack <int> s;
        f1(i, m){
            while(s.size() && b[s.top()] >= b[i]) s.pop();
            if(s.size()) l[i] = s.top() + 1;
            else l[i] = 1;
            s.push(i);
        }
        while(s.size()) s.pop();
        for(int i = m; i >= 1; i--){
            while(s.size() && b[s.top()] >= b[i]) s.pop();
            if(s.size()) r[i] = s.top() - 1;
            else r[i] = m;
            s.push(i);
        }
        f1(i, m){
            res = max(res, b[i] * (r[i] - l[i] + 1));
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
  
    cin >> m >> n >> k;
    f1(i, m) f1(j, n) cin >> arr[i][j], save.push_back(arr[i][j]);
    sort(save.begin(), save.end());
    int lo = 0, ri = save.size() - 1;
    int ans1 = 0, ans2 = 0;
    while(lo <= ri){
        int mid = (lo + ri)/2;
        int g = check(save[mid]);
        if(g >= k) ans1 = save[mid], ans2 = g, lo = mid + 1;
        else ri = mid - 1;
    }
    cout << ans1 << " " << ans2;
}

• Subtask 1: 100 / 100