Submission #241560

#	Time	Username	Problem	Language	Result	Execution time	Memory
241560		davi_bart	Quality Of Living (IOI10_quality)	C++14	100 / 100	2546 ms	85448 KiB

quality

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#define ll long long
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int x[3001][3001];
bool c(int k,int R,int C,int H,int W,int Q[3001][3001]){
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=0;
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=Q[i][j]<k;
      if(j>0)x[i][j]+=x[i][j-1];
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      if(i>0)x[i][j]+=x[i-1][j];
    }
  }
  for(int i=H-1;i<R;i++){
    for(int j=W-1;j<C;j++){
      int z=x[i][j];
      if(i>H-1)z-=x[i-H][j];
      if(j>W-1)z-=x[i][j-W];
      if(i>=H && j>=W)z+=x[i-H][j-W];
      if(z>=(H*W/2)){
          return 1;
      }
    }
  }
  return 0;
}
int sol(int k,int R,int C,int H,int W,int Q[3001][3001]){
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=0;
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=Q[i][j]<k;
      if(j>0)x[i][j]+=x[i][j-1];
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      if(i>0)x[i][j]+=x[i-1][j];
    }
  }
  int mi=1000000000;
  for(int i=H-1;i<R;i++){
    for(int j=W-1;j<C;j++){
      int z=x[i][j];
      if(i>H-1)z-=x[i-H][j];
      if(j>W-1)z-=x[i][j-W];
      if(i>=H && j>=W)z+=x[i-H][j-W];
      if(z>=(H*W/2)){
          for(int a=i-H+1;a<=i;a++){
            for(int b=j-W+1;b<=j;b++){
              if(Q[a][b]>=k)mi=min(mi,Q[a][b]);
            }
          }
      }
    }
  }
  return mi;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001]) {
	int l=1,r=R*C+1;
	while(l<r-1){
    int m=(l+r)/2;
    if(c(m,R,C,H,W,Q))r=m;
    else l=m;
	}
	return sol(r,R,C,H,W,Q);
}/*
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int R,C,H,W;
    cin>>R>>C>>H>>W;
    int Q[3001][3001];
    for(int i=0;i<R;i++){
      for(int j=0;j<C;j++){
        cin>>Q[i][j];
      }
    }
    cout<<rectangle(R,C,H,W,Q);
}*/
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20