Submission #994487

#	Time	Username	Problem	Language	Result	Execution time	Memory
994487		tch1cherin	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	317 ms	21884 KiB

burrow

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, K;
  cin >> N >> M >> K;
  vector<vector<int>> A(N, vector<int>(M));
  vector<int> sorted_vals(N * M);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> A[i][j];
      sorted_vals[i * M + j] = A[i][j];
    }
  }
  sort(sorted_vals.begin(), sorted_vals.end());
  vector<vector<int>> up(N, vector<int>(M));
  vector<int> prv(M), nxt(M);
  int L = -1, R = (int)sorted_vals.size();
  int area;
  while (R - L > 1) {
    int mid = (L + R) / 2;
    int pivot = sorted_vals[mid];
    int max_area = 0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        up[i][j] = (A[i][j] >= pivot ? (i > 0 ? up[i - 1][j] : 0) + 1 : 0);
      }
      for (int j = 0; j < M; j++) {
        prv[j] = j - 1;
        while (prv[j] >= 0 && up[i][prv[j]] > up[i][j]) {
          prv[j] = prv[prv[j]];
        }
      }
      for (int j = M - 1; j >= 0; j--) {
        nxt[j] = j + 1;
        while (nxt[j] < M && up[i][nxt[j]] >= up[i][j]) {
          nxt[j] = nxt[nxt[j]];
        }
        max_area = max(max_area, (nxt[j] - prv[j] - 1) * up[i][j]);
      }
    }
    if (max_area >= K) {
      L = mid;
      area = max_area;
    } else {
      R = mid;
    }
  }
  cout << sorted_vals[L] << " " << area << "\n";
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:50:44: warning: 'area' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |   cout << sorted_vals[L] << " " << area << "\n";
      |                                            ^~~~

• Subtask 1: 100 / 100