Submission #400484

#TimeUsernameProblemLanguageResultExecution timeMemory
400484LawlietLuxury burrow (IZhO13_burrow)C++17
0 / 100
2078 ms332 KiB
#include <bits/stdc++.h> #define MAX 1010 #define INF 1000000010 using namespace std; int n, m, k; int L[MAX]; int R[MAX]; int v[MAX][MAX]; int histogram[MAX]; int largestRectangle() { for(int g = 1 ; g <= m ; g++) { int cur = g - 1; while(histogram[g] <= histogram[cur]) cur = L[cur]; L[g] = cur; } for(int g = m ; g >= 1 ; g--) { int cur = g + 1; while(histogram[g] <= histogram[cur]) cur = R[cur]; R[g] = cur; } int ans = 0; for(int g = 1 ; g <= m ; g++) ans = max(ans , histogram[g]*(R[g] - L[g] - 1)); return ans; } bool test(int l, int t = 0) { int ans = -1; memset(histogram , 0 , sizeof(histogram)); histogram[0] = histogram[m + 1] = -INF; for(int g = 1 ; g <= n ; g++) { for(int h = 1 ; h <= m ; h++) { if(v[g][h] >= l) histogram[h]++; else histogram[h] = 0; } ans = max(ans , largestRectangle()); } if(t == 1) printf("%d\n",ans); return ans >= k; } int bs() { int l = 0, r = INF; int ans; while(l < r) { int m = (l + r)/2; if( test(m) ) l = m; else r = m - 1; } return l; } void init() { L[0] = 0; R[m + 1] = m + 1; } int main() { scanf("%d %d %d",&n,&m,&k); init(); for(int g = 1 ; g <= n ; g++) for(int h = 1 ; h <= m ; h++) scanf("%d",&v[g][h]); int ans = bs(); printf("%d ",ans); test(ans , 1); }

Compilation message (stderr)

burrow.cpp: In function 'int bs()':
burrow.cpp:69:6: warning: unused variable 'ans' [-Wunused-variable]
   69 |  int ans;
      |      ^~~
burrow.cpp: In function 'int main()':
burrow.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d %d %d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
burrow.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |    scanf("%d",&v[g][h]);
      |    ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...