Submission #978138

#	Time	Username	Problem	Language	Result	Execution time	Memory
978138		MilosMilutinovic	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	915 ms	18260 KiB

burrow

#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 / 100