Submission #389567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
389567	2021-04-14T07:33:38 Z	knightron0	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	519 ms	23372 KB

burrow

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e3 + 5;

int n, m, k;
int a[MAXN][MAXN], val[MAXN][MAXN];

int max_area(vector<int> vec){
    stack<int> s;
    int ans = 0;
    int i = 0;
    while(i < m){
        if(s.empty()){ 
            s.push(i);
        } else {
            if(vec[s.top()] > vec[i]){
                int h = vec[s.top()];
                s.pop();
                int res;
                if(s.empty()){
                    res = h * i;
                } else {
                    res = h * (i-(s.top() +1));
                }
                ans = max(ans, res);
                continue;
            } else {
                s.push(i);
            }
        }
        i++;
    }
    while(!s.empty()){
        int h = vec[s.top()];
        s.pop();
        int res;
        if(s.empty()){
            res = h * i;
        } else {
            res = h * (i-(s.top() +1));
        }
        ans = max(ans, res);
    }
    return ans;
}


int check(int x){
    for(int i= 0;i<n;i++){
        for(int j= 0;j<m;j++){
            if(a[i][j] >= x){
                val[i][j] = 1;
            } else {
                val[i][j]= 0;
            }
        }
    }
    vector<int> v;
    for(int i=0;i<m;i++){
        v.pb(val[0][i]);
    }
    int ans = max_area(v);
    for(int i= 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(val[i][j] && i > 0){
                val[i][j] += val[i - 1][j];
            }
        }
        v.clear();
        for(int j=0;j<m;j++){
            v.pb(val[i][j]);
        }
        ans = max(ans, max_area(v));
    }
    return ans;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    cin>>n>>m>>k;
    for(int i= 0;i<n;i++){
        for(int j= 0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int lo =0;
    int ans= 0;
    int hi = 1e9;
    while(lo < hi){
        int m = (lo + hi)/2;
        int sz = check(m);
        if(sz >= k){
            lo = m+1;
            ans = max(ans, m);
        } else {
            hi = m-1;
        }
    }
    if(check(lo) >= k) ans = max(lo, ans);
    if(check(hi) >= k) ans = max(hi, ans);
    cout<<ans<<' '<<check(ans)<<endl;
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	460 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	1 ms	580 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	6 ms	1228 KB	Output is correct
9	Correct	10 ms	2380 KB	Output is correct
10	Correct	24 ms	2764 KB	Output is correct
11	Correct	38 ms	3788 KB	Output is correct
12	Correct	25 ms	5276 KB	Output is correct
13	Correct	31 ms	2244 KB	Output is correct
14	Correct	91 ms	6604 KB	Output is correct
15	Correct	80 ms	6604 KB	Output is correct
16	Correct	82 ms	7116 KB	Output is correct
17	Correct	107 ms	8644 KB	Output is correct
18	Correct	198 ms	12560 KB	Output is correct
19	Correct	271 ms	13252 KB	Output is correct
20	Correct	404 ms	18364 KB	Output is correct
21	Correct	431 ms	20804 KB	Output is correct
22	Correct	519 ms	23372 KB	Output is correct
23	Correct	513 ms	23340 KB	Output is correct
24	Correct	390 ms	18172 KB	Output is correct
25	Correct	465 ms	18884 KB	Output is correct