답안 #341661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341661 2020-12-30T11:06:02 Z tengiz05 호화 벙커 (IZhO13_burrow) C++17
100 / 100
861 ms 24044 KB
#include <bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
template<class T> bool chmin(T& a, const T& b){return a>b?a=b,true:false;}
template<class T> bool chmax(T& a, const T& b){return a<b?a=b,true:false;}
const int N = 1005;
const int inf = 100200300;
int n, m, k;
int a[N][N], inp[N][N];
int h[N][N];
void Solve(){
  cin >> n >> m >> k;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin >> inp[i][j];
    }
  }
  int L = -1, R = inf+inf;
  int resmn = 0, resmx = 0;
  int iter = 0;
  while(L+1 < R){
    int mid = L+R>>1;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        if(inp[i][j] >= mid){
          a[i][j] = 1;
        }else a[i][j] = 0;
      }
    }
    // start fermer-2 ------------------------
    int ans = 0;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        if(a[i][j] == 0)h[i][j] = 0;
        else h[i][j] = h[i-1][j] + 1;
      }
    }
    for(int i=1;i<=n;i++){
      vector<int> v;
      vector<int> l(m+2), r(m+2);
      v.push_back(0);
      for(int j=1;j<=m;j++){
        v.push_back(h[i][j]);
      }
      vector<pair<int, int>> q;
      q.push_back({0, 0});
      for(int j=1;j<=m;j++){
        if(v[j] == 0)q.clear(),q.push_back({0, j});
        else {
          while(q.back().first >= v[j])q.pop_back();
          int lst = q.back().second;
          l[j] = lst;
          q.push_back({v[j], j});
        }
      }
      q.clear();
      q.push_back({0,m+1});
      for(int j=m;j>=1;j--){
        if(v[j] == 0)q.clear(),q.push_back({0, j});
        else {
          while(q.back().first >= v[j])q.pop_back();
          int lst = q.back().second;
          r[j] = lst;
          q.push_back({v[j], j});
        }
      }
      for(int j=1;j<=m;j++){
        chmax(ans, (r[j]-l[j]-1)*v[j]);
      }
    }// end fermer-2 ------------------------

    if(ans >= k){
      L = mid;
      if(mid >= resmn){
        resmn = mid;
        resmx = ans;
      }
    }else R = mid;
  }
  cout << resmn << ' ' << resmx << '\n';
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie();
  int t=1;
  while(t--)Solve();
  return 0;
}

Compilation message

burrow.cpp: In function 'void Solve()':
burrow.cpp:24:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int mid = L+R>>1;
      |               ~^~
burrow.cpp:22:7: warning: unused variable 'iter' [-Wunused-variable]
   22 |   int iter = 0;
      |       ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 9 ms 1772 KB Output is correct
9 Correct 18 ms 3180 KB Output is correct
10 Correct 39 ms 3692 KB Output is correct
11 Correct 71 ms 4844 KB Output is correct
12 Correct 43 ms 7532 KB Output is correct
13 Correct 49 ms 2796 KB Output is correct
14 Correct 129 ms 8940 KB Output is correct
15 Correct 127 ms 8940 KB Output is correct
16 Correct 145 ms 9068 KB Output is correct
17 Correct 172 ms 12140 KB Output is correct
18 Correct 347 ms 14680 KB Output is correct
19 Correct 392 ms 17004 KB Output is correct
20 Correct 741 ms 19440 KB Output is correct
21 Correct 703 ms 21596 KB Output is correct
22 Correct 821 ms 24044 KB Output is correct
23 Correct 861 ms 24044 KB Output is correct
24 Correct 621 ms 23020 KB Output is correct
25 Correct 651 ms 24044 KB Output is correct