# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
431542 | 2021-06-17T12:50:48 Z | APROHACK | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KB |
#include "quality.h" #include <bits/stdc++.h> #define PB push_back using namespace std; int Rg, Cg, Hg, Wg; int sum[3005][3005], q[3005][3005]; //unordered_map<int, bool>a; /* int sumar(int i, int j, int dd, int htt){ if(dd<-1||htt<-1)return -1; return sum[i][j]-((htt>=0 ? sum[i][htt] : 0)+(dd>=0?sum[dd][j]:0))+(dd>=0&&htt>=0 ? sum[dd][htt] : 0); } */ bool check(int x){ //cout<<"x = "<<x<<endl; /* for(int i = 0 ; i < Rg ; i++){ sum[i][0]= }*/ for(int i = 0 ; i < Rg ; i++){ sum[i][0]=(q[i][0] <= x ? 1:-1); for(int j = 1 ; j < Cg ; j++){ sum[i][j]=sum[i][j-1]+(q[i][j] <= x ? 1:-1); } } /* for(int i = 0 ; i < Rg ; i ++){ for(int j = 0 ; j < Cg ; j++){ cout<<sum[i][j]<<" "; } cout<<endl; }*/ for(int j = 0 ; j < Cg ; j++){ sum[0][j]; if(sumar(0, j, 0-Hg, 0-Wg)>0)return true; for(int i = 1 ; i < Rg ; i++){ sum[i][j]+=sum[i-1][j]; if(((i-Hg<-1||j-Wg<-1) ? -1 : (sum[i][j]-((j-Wg>=0 ? sum[i][j-Wg] : 0)+(i-Hg>=0?sum[i-Hg][j]:0))+(i-Hg>=0&&j-Wg>=0 ? sum[i-Hg][j-Wg] : 0)))>0)return true; //cout<<i<<" "<<j<<" = "<<sum[i][j]<<" "; } //cout<<endl; } return false; } int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { Rg=R, Cg=C, Hg=H, Wg=W; int minimum = INT_MAX; int li = 1, ls = R*C, pos; pos=(li+ls)/2; for(int i = 0 ; i < R ; ++i){ for(int j = 0 ; j < C ; ++j){ q[i][j]=Q[i][j]; } } while(li!=ls){ //cout<<li<<" "<<ls<<endl; pos=(li+ls)/2; //a[pos]=check(pos); if(check(pos))ls=pos; else li=pos+1; } /* for(int i = ls ; i >= li ; i--){ //bool dou = ((a.find(i)==a.end())?check(i):a[i]); if(check(i))pos=i; }*/ return li; }