oj.uz

Submission #341659

# Submission time Handle Problem Language Result Execution time Memory
341659 2020-12-30T11:05:29 Z tengiz05 Luxury burrow (IZhO13_burrow) C++17
100 / 100
 974 ms 24172 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(iter < 34){
    iter++;
    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:25:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = L+R>>1;
      |               ~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory 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 12 ms 1772 KB Output is correct
9 Correct 21 ms 3180 KB Output is correct
10 Correct 46 ms 3692 KB Output is correct
11 Correct 78 ms 4844 KB Output is correct
12 Correct 56 ms 7532 KB Output is correct
13 Correct 58 ms 2668 KB Output is correct
14 Correct 157 ms 8940 KB Output is correct
15 Correct 167 ms 8940 KB Output is correct
16 Correct 197 ms 9196 KB Output is correct
17 Correct 207 ms 12268 KB Output is correct
18 Correct 415 ms 14572 KB Output is correct
19 Correct 511 ms 16876 KB Output is correct
20 Correct 844 ms 19308 KB Output is correct
21 Correct 811 ms 21740 KB Output is correct
22 Correct 940 ms 24172 KB Output is correct
23 Correct 974 ms 24044 KB Output is correct
24 Correct 772 ms 22892 KB Output is correct
25 Correct 833 ms 24172 KB Output is correct