답안 #389567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389567 2021-04-14T07:33:38 Z knightron0 호화 벙커 (IZhO13_burrow) C++14
100 / 100
519 ms 23372 KB
#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;
}
# 결과 실행 시간 메모리 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