Submission #341661

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341661	2020-12-30T11:06:02 Z	tengiz05	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	861 ms	24044 KB

burrow

#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(L+1 < R){
    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:24:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int mid = L+R>>1;
      |               ~^~
burrow.cpp:22:7: warning: unused variable 'iter' [-Wunused-variable]
   22 |   int iter = 0;
      |       ^~~~

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	9 ms	1772 KB	Output is correct
9	Correct	18 ms	3180 KB	Output is correct
10	Correct	39 ms	3692 KB	Output is correct
11	Correct	71 ms	4844 KB	Output is correct
12	Correct	43 ms	7532 KB	Output is correct
13	Correct	49 ms	2796 KB	Output is correct
14	Correct	129 ms	8940 KB	Output is correct
15	Correct	127 ms	8940 KB	Output is correct
16	Correct	145 ms	9068 KB	Output is correct
17	Correct	172 ms	12140 KB	Output is correct
18	Correct	347 ms	14680 KB	Output is correct
19	Correct	392 ms	17004 KB	Output is correct
20	Correct	741 ms	19440 KB	Output is correct
21	Correct	703 ms	21596 KB	Output is correct
22	Correct	821 ms	24044 KB	Output is correct
23	Correct	861 ms	24044 KB	Output is correct
24	Correct	621 ms	23020 KB	Output is correct
25	Correct	651 ms	24044 KB	Output is correct