Submission #1272942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272942		meisgood	Quality Of Living (IOI10_quality)	C++20	100 / 100	1041 ms	106208 KiB

quality

#include <bits/stdc++.h>
using namespace std ;
#define ll long long
// #define test
#ifndef test
#include "quality.h"

#endif
////////////////////////////////////////////////////////////////////////
int A[3003][3003] ;
int ps[3003][3003] ;
int R,C,H,W ;
bool check(int x){
  int i,j ;
  for (i = 0 ; i < 3003 ; i ++) for (j = 0 ; j < 3003 ; j ++) ps[i][j]=0 ;
  for (i = 1 ; i <= R ; i ++){
    for (j = 1 ; j <= C ; j ++) ps[i][j]=ps[i][j-1]+(A[i][j]<=x) ;
    for (j = 1 ; j <= C ; j ++) ps[i][j]+=ps[i-1][j] ;
  }
  for (i = 1 ; i <= R ; i ++){
    for (j = 1 ; j <= C ; j ++){
      if (i+H-1<=R&&j+W-1<=C){
        if (ps[i+H-1][j+W-1]-ps[i+H-1][j-1]-ps[i-1][j+W-1]+ps[i-1][j-1]>=(H*W+1)/2) return 1 ;
      }
    }
  }
  return 0 ;
}
int rectangle(int r2, int c, int h, int w, int Q[3001][3001]) {
  R=r2,C=c,H=h,W=w ;
  int i,j ;
  for (i = 1 ; i <= R ; i ++) for (j = 1 ; j <= C ; j ++) A[i][j]=Q[i-1][j-1] ;
  int l=0,r=R*C ;
  while (l<r){
    int md=(l+r)/2 ;
    if (check(md)) r=md ;
    else l=md+1 ;
  }
	return l;
}

////////////////////////////////////////////////////////////////////////
#ifdef test
//grader{
#include <stdio.h>
#include <stdlib.h>

static int R1,C1,H1,W1,Q[3001][3001],i,j,ans;
int main(){
   scanf("%d%d%d%d",&R1,&C1,&H1,&W1);
   for (i=0;i<R1;i++) for (j=0;j<C1;j++) scanf("%d",&Q[i][j]);
   ans = rectangle(R1,C1,H1,W1,Q);
   printf("%d\n",ans);
   return 0;
}


//grader}
#endif

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