# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1105583 | andrewp | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int n, int m, int H, int W, int A[3001][3001]){
int a[n+10][m+10];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=A[i-1][j-1];
int bot=1,top=n*m,ans;
while(bot<=top){
int mid=l+r>>1;
int ps[n+10][m+10];
for(int i=0;i<n+10;i++) for(int j=0;j<m+10;j++) ps[i][j]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1];
if(A[i][j]>mid) ps[i][j]++;
}
}
int val=m*n+50;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i<H||j<W) continue;
val=min(val,ps[i][j]-ps[i-H][j]-ps[i][j-W]+ps[i-H][j-W]);
}
}
if(val<=H*W/2){
res=mid;
top=mid-1;
}
else bot=mid+1;
}
return ans;
}