oj.uz

Submission #341651

# Submission time Handle Problem Language Result Execution time Memory
341651 2020-12-30T11:01:07 Z tengiz05 Luxury burrow (IZhO13_burrow) C++17
0 / 100
 2000 ms 9452 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(true){
    iter++;
    if(iter > 1000)break;
    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:26:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = L+R>>1;
      |               ~^~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 7 ms 492 KB Output is correct
4 Correct 15 ms 620 KB Output is correct
5 Correct 31 ms 748 KB Output is correct
6 Correct 58 ms 876 KB Output is correct
7 Correct 27 ms 492 KB Output is correct
8 Correct 354 ms 1900 KB Output is correct
9 Correct 527 ms 3308 KB Output is correct
10 Correct 1197 ms 4076 KB Output is correct
11 Correct 1937 ms 5612 KB Output is correct
12 Correct 1819 ms 7788 KB Output is correct
13 Correct 1448 ms 3180 KB Output is correct
14 Execution timed out 2082 ms 9452 KB Time limit exceeded
15 Halted 0 ms 0 KB -