Submission #672983

#TimeUsernameProblemLanguageResultExecution timeMemory
672983Alihan_8Luxury burrow (IZhO13_burrow)C++17
100 / 100
682 ms25676 KiB
#include <bits/stdc++.h> // include <ext/pb_ds/assoc_container.hpp> // include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; #define all(x) x.begin(), x.end() #define pb push_back // define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> #define mpr make_pair #define ln '\n' void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} #define int long long signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, k; cin >> n >> m >> k; vector <vector<int>> p(n); for ( auto &i: p ){ i.resize(m); for ( auto &j: i ) cin >> j; } auto chmax = [&](int &l, int r){l = max(l, r);}; auto calc = [&](vector <int> &x){ auto f = [&](){ stack <int> stk; vector <int> res(m); stk.push(-1); for ( int i = 0; i < m; i++ ){ while ( stk.top() != -1 and x[stk.top()] >= x[i] ) stk.pop(); res[i] = stk.top()+1; stk.push(i); } return res; }; vector <int> l = f(); reverse(all(x)); vector <int> r = f(); reverse(all(x)); for ( int i = 0; i < m; i++ ) r[i] = m-1-r[i]; reverse(all(r)); int Mx = 0; for ( int i = 0; i < m; i++ ) chmax(Mx, (r[i]-l[i]+1)*x[i]); return Mx; }; auto f = [&](int T){ vector <vector<int>> bits(n, vector <int> (m)); for ( int i = 0; i < n; i++ ){ for ( int j = 0; j < m; j++ ){ bits[i][j] = p[i][j] >= T; } } vector <int> x(m); int Mx = 0; for ( int i = 0; i < n; i++ ){ for ( int j = 0; j < m; j++ ){ if ( bits[i][j] ) x[j]++; else x[j] = 0; } chmax(Mx, calc(x)); } return Mx; }; int l = 1, r = 1e9+1; while ( l+1 < r ){ int md = (l+r)>>1; if ( f(md) < k ) r = md; else l = md; } cout << l << ' ' << f(l); cout << '\n'; }

Compilation message (stderr)

burrow.cpp: In function 'void IO(std::string)':
burrow.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...