Submission #490059

#	Time	Username	Problem	Language	Result	Execution time	Memory
490059		Valera_Grinenko	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	286 ms	13852 KiB

burrow

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main() {

  ios::sync_with_stdio(0); cin.tie(0);

  int n, m, k;

  cin >> n >> m >> k;

  vector<vector<int> > a(n, vector<int>(m));

  for(auto& x : a)
    for(auto& y : x)
      cin >> y;

  int l = 1, r = 1e9 + 42;

  while(l < r) {
    int mb = (l + r + 1) / 2;
    vector<int> cur(m);
    int mx = 0;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if(a[i][j] >= mb) cur[j]++;
        else cur[j] = 0;
      }
      stack<int> st;
      int top = 0, ar = 0;
      int in = 0;
      while(in < m) {
        if(st.empty() || cur[st.top()] <= cur[in]) st.push(in++);
        else {
          top = cur[st.top()];
          st.pop();
          ar = top * in;
          if(!st.empty()) ar = top * (in - st.top() - 1);
          mx = max(mx, ar);
        }
      }
      while(!st.empty()) {
        top = cur[st.top()];
        st.pop();
        ar = top * in;
        if(!st.empty()) ar = top * (in - st.top() - 1);
        mx = max(mx, ar);
      }
    }
    if(mx >= k) l = mb;
    else r = mb - 1;
  }

  cout << l << ' ';

  vector<int> cur(m);

  int mx = 0;

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      if(a[i][j] >= l) cur[j]++;
      else cur[j] = 0;
    }
    stack<int> st;
    int top = 0, ar = 0;
    int in = 0;
    while(in < m) {
      if(st.empty() || cur[st.top()] <= cur[in]) st.push(in++);
      else {
        top = cur[st.top()];
        st.pop();
        ar = top * in;
        if(!st.empty()) ar = top * (in - st.top() - 1);
        mx = max(mx, ar);
      }
    }
    while(!st.empty()) {
      top = cur[st.top()];
      st.pop();
      ar = top * in;
      if(!st.empty()) ar = top * (in - st.top() - 1);
      mx = max(mx, ar);
    }
  }

  cout << mx << '\n';

  return 0;
}
/*

*/

Compilation message (stderr)

burrow.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 100 / 100