# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
512646 | 2022-01-16T15:26:36 Z | algorithm16 | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KB |
#include "quality.h" int sum[3005][3005]; int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { int r=R,c=C,h=H,w=W; int lo=1,hi=r*c; while(lo<hi) { int mid=(lo+hi)/2; int s=0,cnt=0; for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { if(Q[i][j]<=mid) s+=1; else s-=1; sum[i][j]=s; if(i) sum[i][j]+=sum[i-1][j]; } } for(int i=0;i+h-1<r;i++) { for(int j=0;j+w-1<c;j++) { if(get_sum(i,j,i+h-1,j+w-1)>0) cnt+=1; } } if(cnt) hi=mid; else lo=mid+1; } return lo; }