oj.uz

답안 #340476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340476 2020-12-27T17:11:47 Z tengiz05 호화 벙커 (IZhO13_burrow) C++17
0 / 100
 30 ms 8300 KB 
#include <bits/stdc++.h>
#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;
  int resmn = 0, resmx = 0;
  while(L+1 < R){
    int mid = L+R>>1;
    memset(a, 0, sizeof a);
    memset(h, 0, sizeof h);
    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;
        chmax(ans, h[i][j]);
      }
    }
    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.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.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:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = L+R>>1;
      |               ~^~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 8300 KB Output is correct
2 Incorrect 29 ms 8300 KB Output isn't correct
3 Halted 0 ms 0 KB -