Submission #340460

#	Time	Username	Problem	Language	Result	Execution time	Memory
340460		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){
   // cout << l << ' ' << r << '\n';
    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;
      v.push_back(0);
      for(int j=1;j<=m;j++){
        v.push_back(h[i][j]);
      }
      vector<pair<int, int>> q;
      for(int j=1;j<=m;j++){
        int lst = j;
        while(q.size() && q.back().first >= v[j]){
          lst = q.back().second;
          q.pop_back();
        }
        if(v[j] > 0)q.push_back({v[j], lst});
        if(q.size() > 1){
          auto [x2, y2] = q[q.size()-1];
          auto [x1, y1] = q[q.size()-2];
          chmax(ans, (y2-y1+1)*x1);
          chmax(ans, (j-y1+1)*x1);
        }
        if(q.size()){
          auto [x1, y1] = q[q.size()-1];
          chmax(ans, (j-y1+1)*x1);
        }
      }
    }
    for(int i=1;i<=n;i++){
      vector<int> v;
      v.push_back(0);
      for(int j=m;j>=1;j--){
        v.push_back(h[i][j]);
      }
      vector<pair<int, int>> q;
      for(int j=1;j<=m;j++){
        int lst = j;
        while(q.size() && q.back().first >= v[j]){
          lst = q.back().second;
          q.pop_back();
        }
        if(v[j] > 0)q.push_back({v[j], lst});
        if(q.size() > 1){
          auto [x2, y2] = q[q.size()-1];
          auto [x1, y1] = q[q.size()-2];
          chmax(ans, (y2-y1+1)*x1);
          chmax(ans, (j-y1+1)*x1);
        }if(q.size()){
          auto [x1, y1] = q[q.size()-1];
          chmax(ans, (j-y1+1)*x1);
        }
      }
    }// 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