Submission #341661

#TimeUsernameProblemLanguageResultExecution timeMemory
341661tengiz05Luxury burrow (IZhO13_burrow)C++17
100 / 100
861 ms24044 KiB
#include <bits/stdc++.h> #define int long long #define all(x) (x).begin(), (x).end() typedef long long ll; using namespace std; template<class T> bool chmin(T& a, const T& b){return a>b?a=b,true:false;} template<class T> bool chmax(T& a, const T& b){return a<b?a=b,true:false;} const int N = 1005; const int inf = 100200300; int n, m, k; int a[N][N], inp[N][N]; int h[N][N]; void Solve(){ cin >> n >> m >> k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin >> inp[i][j]; } } int L = -1, R = inf+inf; int resmn = 0, resmx = 0; int iter = 0; while(L+1 < R){ int mid = L+R>>1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(inp[i][j] >= mid){ a[i][j] = 1; }else a[i][j] = 0; } } // start fermer-2 ------------------------ int ans = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j] == 0)h[i][j] = 0; else h[i][j] = h[i-1][j] + 1; } } for(int i=1;i<=n;i++){ vector<int> v; vector<int> l(m+2), r(m+2); v.push_back(0); for(int j=1;j<=m;j++){ v.push_back(h[i][j]); } vector<pair<int, int>> q; q.push_back({0, 0}); for(int j=1;j<=m;j++){ if(v[j] == 0)q.clear(),q.push_back({0, j}); else { while(q.back().first >= v[j])q.pop_back(); int lst = q.back().second; l[j] = lst; q.push_back({v[j], j}); } } q.clear(); q.push_back({0,m+1}); for(int j=m;j>=1;j--){ if(v[j] == 0)q.clear(),q.push_back({0, j}); else { while(q.back().first >= v[j])q.pop_back(); int lst = q.back().second; r[j] = lst; q.push_back({v[j], j}); } } for(int j=1;j<=m;j++){ chmax(ans, (r[j]-l[j]-1)*v[j]); } }// end fermer-2 ------------------------ if(ans >= k){ L = mid; if(mid >= resmn){ resmn = mid; resmx = ans; } }else R = mid; } cout << resmn << ' ' << resmx << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(); int t=1; while(t--)Solve(); return 0; }

Compilation message (stderr)

burrow.cpp: In function 'void Solve()':
burrow.cpp:24:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int mid = L+R>>1;
      |               ~^~
burrow.cpp:22:7: warning: unused variable 'iter' [-Wunused-variable]
   22 |   int iter = 0;
      |       ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...