# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
587364 | 2022-07-01T17:28:16 Z | HeyYouNotYouYou | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KB |
#include "quality.h" #include "grader.cpp" #include <bits/stdc++.h> using namespace std; int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { int n = R , m = C; int l = 1 , r = R*C, ans = R*C; while(l<=r) { int mid = (l+r)/2; //cout<<mid<<endl; int less[n+1][m+1]={0} , more[n+1][m+1]={0},cursmall=0,curbig=0; memset(less,0,sizeof less); memset(more,0,sizeof more); for(int i = 1 ; i <= n ; i ++) { for(int j = 1 ; j <= m ; j ++) { less[i][j] = less[i-1][j] + less[i][j-1] - less[i-1][j-1] + (Q[i-1][j-1]<mid); more[i][j] = more[i-1][j] + more[i][j-1] - more[i-1][j-1] + (Q[i-1][j-1]>mid); } } int ok = 0; for(int i = 1 ; i <= n-H+1 ; i ++) { for(int j = 1 ; j <= m-W+1 ; j ++) { //cout<<mid<<" "<<i+H-1<<" "<<j+W-1<<endl; int olayel = less[i+H-1][j+W-1] - less[i-1][j+W-1] - less[i+H-1][j-1] + less[i-1][j-1]; int kteer = more[i+H-1][j+W-1] - more[i-1][j+W-1] - more[i+H-1][j-1] + more[i-1][j-1]; if(olayel == kteer && olayel == (H*W)/2) { //cout<<"!"<<i<<" "<<j<<" "<<olayel<<" "<<kteer<<endl; ans=min(ans,mid),ok=1; } if(olayel >= kteer) ok=1; } } if(ok){ r = mid-1; } else{ l = mid+1; } } return ans; }