Submission #340472

#	Time	Username	Problem	Language	Result	Execution time	Memory
340472		tengiz05	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	1 ms	364 KiB

burrow

#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)/2;
    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+1), r(m+1);
      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(chmax(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;
}

• Subtask 1: 0 / 100