Submission #673579

#TimeUsernameProblemLanguageResultExecution timeMemory
673579BaytoroLuxury burrow (IZhO13_burrow)C++17
100 / 100
1036 ms25760 KiB
#include <bits/stdc++.h> using namespace std; #define ios ios::sync_with_stdio(false); cin.tie(NULL); #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define fr first #define sc second #define int long long #define endl '\n' void fopn(string name){ freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } const int INF=1e18,mod=998244353; int n,m,k; int h[1005][1005],a[1005][1005]; int area=0; int get_area(vector<int> vec){ int N=vec.size(); vec.resize(N+2); vector<int> l(N+2),r(N+2); vec[0]=vec[N+1]=-INF; stack<int> st; st.push(0); for(int i=1;i<=N;i++){ while(vec[st.top()]>vec[i]) st.pop(); l[i]=st.top(); st.push(i); } while(!st.empty()) st.pop(); st.push(N+1); for(int i=N;i>0;i--){ while(vec[st.top()]>=vec[i]) st.pop(); r[i]=st.top()-1; st.push(i); } int res=0; for(int i=1;i<=N;i++) res=max(res,(r[i]-l[i])*vec[i]); return res; } bool check(int md){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(h[i][j]>=md) a[i][j]=1; else a[i][j]=0; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) if(a[i][j]) a[i][j]+=a[i-1][j]; } area=0; for(int i=1;i<=n;i++){ vector<int> v; v.pb(0); for(int j=1;j<=m+1;j++){ v.pb(a[i][j]); } area=max(area,get_area(v)); } if(area>=k) return 1; return 0; } void solve(){ cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>h[i][j]; int l=0,r=1e9; int ar=0,ans=0; while(r-l>1){ //cout<<l<<' '<<r<<' '; int md=(l+r)/2; if(check(md)){ l=md; ans=md,ar=area; } else r=md; //cout<<area<<endl; } cout<<ans<<' '<<ar<<endl; } main(){ //fopn("newbarn"); //ios; int T=1; //cin>>T; while(T--){ solve(); } }

Compilation message (stderr)

burrow.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main(){
      | ^~~~
burrow.cpp: In function 'void fopn(std::string)':
burrow.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...