| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1348380 | dimitar | Quality Of Living (IOI10_quality) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define maxn 3005
using namespace std;
int r,c,h,w;
int q[maxn][maxn];
int pref[maxn][maxn];
void read()
{
cin>>r>>c>>h>>w;
for(int i=1; i<=r; i++)
{
for(int j=1; j<=c; j++)cin>>q[i][j];
}
}
bool check(int x)
{
for(int i=0; i<=r; i++)
{
for(int j=0; j<=c; j++)pref[i][j]=0;
}
for(int i=1; i<=r; i++)
{
for(int j=1; j<=c; j++)
{
pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
if(q[i][j]<=x)pref[i][j]++;
else pref[i][j]--;
}
}
for(int i=h; i<=r; i++)
{
for(int j=w; j<=c; j++)
{
int sum=pref[i][j]-pref[i-h][j]-pref[i][j-w]+pref[i-h][j-w];
if(sum>0)return 1;
}
}
return 0;
}
int main()
{
read();
int l=1,rt=r*c;
while(l<rt)
{
int mid=(l+rt)/2;
if(check(mid))rt=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
