oj.uz

Submission #978138

# Submission time Handle Problem Language Result Execution time Memory
978138 2024-05-08T22:46:23 Z MilosMilutinovic Luxury burrow (IZhO13_burrow) C++14
100 / 100
 915 ms 18260 KB 
#include <bits/stdc++.h>

using namespace std;

class dsu {
 public: 
  vector<int> p;
  vector<int> sz;

  dsu(int n) {
    p.resize(n);
    sz.resize(n);

    iota(p.begin(), p.end(), 0);
    fill(sz.begin(), sz.end(), 1);
  }

  int get(int x) {
    return (p[x] == x ? x : p[x] = get(p[x]));
  }

  int get_sz(int x) {
    return sz[get(x)];
  }

  void unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) {
      return;
    }
    if (sz[x] < sz[y]) {
      swap(x, y);
    }
    sz[x] += sz[y];
    p[y] = x;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  auto Solve = [&](int v) {
    int ans = 0;
    vector<vector<int>> b(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (a[i][j] < v) {
          b[i][j] = -1; 
        } else {
          b[i][j] = ((i > 0 && b[i - 1][j] != -1) ? b[i - 1][j] + 1 : 1);
        }
        ans = max(ans, b[i][j]);
      }
    }
    for (int i = 0; i < n; i++) {
      vector<vector<int>> qi(n + 1);
      for (int j = 0; j < m; j++) {
        if (b[i][j] == -1) {
          continue;
        }
        qi[b[i][j]].push_back(j);
      }
      dsu d(m);
      for (int x = n; x >= 1; x--) {
        for (int j : qi[x]) {
          if (j > 0 && b[i][j - 1] >= b[i][j]) {
            d.unite(j - 1, j);
          }
          if (j + 1 < m && b[i][j + 1] >= b[i][j]) {
            d.unite(j + 1, j);
          }
          ans = max(ans, b[i][j] * d.get_sz(j));
        }
      }
    }
    return ans;
  };
  int low = 0, high = 1.00001e9;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    if (Solve(mid) >= k) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  cout << low << " " << Solve(low) << '\n';
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 14 ms 604 KB Output is correct
10 Correct 26 ms 1112 KB Output is correct
11 Correct 91 ms 1368 KB Output is correct
12 Correct 53 ms 1016 KB Output is correct
13 Correct 23 ms 1296 KB Output is correct
14 Correct 95 ms 2328 KB Output is correct
15 Correct 107 ms 2324 KB Output is correct
16 Correct 133 ms 2820 KB Output is correct
17 Correct 63 ms 2972 KB Output is correct
18 Correct 412 ms 6104 KB Output is correct
19 Correct 306 ms 6208 KB Output is correct
20 Correct 883 ms 11168 KB Output is correct
21 Correct 649 ms 13384 KB Output is correct
22 Correct 892 ms 18204 KB Output is correct
23 Correct 915 ms 18260 KB Output is correct
24 Correct 505 ms 9352 KB Output is correct
25 Correct 296 ms 11240 KB Output is correct