Submission #75992

#TimeUsernameProblemLanguageResultExecution timeMemory
75992VardanyanLuxury burrow (IZhO13_burrow)C++14
100 / 100
775 ms30436 KiB
#pragma GCC optimize "-O3" #include <bits/stdc++.h> using namespace std; const int N = 1005; //int t[N][4*N]; int b[N][N]; int a[N][N]; int L[N]; int R[N]; /* void build(int row,int v,int l,int r){ if(l == r){ t[row][v] = a[row][l]; return; } int m = (l+r)/2; build(row,v*2,l,m); build(row,v*2+1,m+1,r); t[row][v] = min(t[row][v*2],t[row][v*2+1]); } int query(int row,int v,int s,int e,int l,int r){ if(l>r) return 1000*1000*1000+5; if(s == l && e == r) return t[row][v]; int m = (s+e)/2; return min(query(row,v*2,s,m,l,min(m,r)),query(row,v*2+1,m+1,e,max(l,m+1),r)); }*/ int n,m,k; inline int get(int x){ int mxs = 0; for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(b[i][j] >= x) a[i][j] = a[i-1][j]+1; else a[i][j] = 0; } } for(int i = 1;i<=n;i++){ memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); for(int j = 1;j<=m;j++){ int u = a[i][j]; int l = j,r = j; L[j] = j; while(l>1){ if(L[l]<l && L[l]) l = L[l]; else l--; if(a[i][l]<u){ l++; break; } } // u*=(r-l+1); // mxs = max(mxs,u); L[j] = l; // R[j] = r; } for(int j = m;j>=1;j--){ int r = j; int u = a[i][j]; while(r<m){ if(R[r]>r) r = R[r]; else r++; if(a[i][r]<u){ r--; break; } } R[j] = r; } for(int j = 1;j<=m;j++) mxs = max(mxs,(R[j]-L[j]+1)*a[i][j]); } return mxs; } int main(){ scanf("%d%d%d",&n,&m,&k); vector<int> all; //map<int,int> mp; for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ scanf("%d",&b[i][j]); // if(!mp[b[i][j]]){ all.push_back(b[i][j]); // mp[b[i][j]] = 1; // } } } sort(all.begin(),all.end()); int l = 0; int r = all.size()-1; int ans = 0; int mxs = k; while(l<=r){ int m = (l+r)/2; int y = get(all[m]); if(y>=k){ ans = m; mxs = y; l = m+1; } else r = m-1; } cout<<all[ans]<<" "<<mxs<<endl; return 0; }

Compilation message (stderr)

burrow.cpp: In function 'int get(int)':
burrow.cpp:41:23: warning: unused variable 'r' [-Wunused-variable]
             int l = j,r = j;
                       ^
burrow.cpp: In function 'int main()':
burrow.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
burrow.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&b[i][j]);
                 ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...