# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
329072 | 2020-11-18T22:50:16 Z | urosk | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define inf 1e15 #define pb push_back #define popb pop_back #define fi first #define sc second #define pii pair<int,int> #define all(a) a.begin(),a.end() #define rall(a) a.begin(),a.end(),greater<int>() using namespace std; int n,m,h,w; #define maxn 3005 int a[maxn][maxn]; int b[maxn][maxn]; bool check(int x){ for(int i = 1;i<=n;i++) fill(b[i],b[i]+m,0); for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1]+(a[i][j]<=x?1:-1); //cout<<b[i][j]<< " "; } //cout<<"\n"; } for(int i = h;i<=n;i++){ for(int j = w;j<=m;j++){ if(b[i][j]-b[i-h][j]-b[i][j-w]+b[i-h][j-w]>0){ /*cout<<a[i][j]<< " "<<a[i-h][j]<<" "<<a[i][j-w]<<" "<< cout<<i<< " "<<j<<"\n";*/ return 1; } } } return 0; } int bs(){ int l = 1,r=maxn*maxn,rez=maxn*maxn,mid; while(l<=r){ mid = (l+r)/2; //cout<<"mid: "<<mid<<"\n"; if(check(mid)){ r = mid-1; rez = mid; }else l = mid+1; } return rez; } int main(){ ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); cin >> n >> m >> h >> w; for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++) cin >> a[i][j]; } cout<<bs(); }