Submission #1199747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199747		SonicML	Quality Of Living (IOI10_quality)	C++20	100 / 100	1556 ms	106136 KiB

quality

#include <iostream>
#include "quality.h"

using namespace std;

int n, m, high, wide;
int const NMAX = 3000;
int mat[1 + NMAX][1 + NMAX];
int presum[1 + NMAX][1 + NMAX];

void buildPresum(int lim) {
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= m;j++) {
      presum[i][j] = presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1];
      if(lim < mat[i][j]) {
	presum[i][j]++;
      }
    }
  }
}

bool isGood() {
  for(int i = high;i <= n;i++) {
    for(int j = wide;j <= m;j++) {
      int sum = presum[i][j] - presum[i-high][j] - presum[i][j-wide] + presum[i-high][j-wide];
      if(sum + sum < high * wide) {
        return true;
      }
    }
  } 
  return false;
}

int cautbin(int from, int to) {
  if(from >= to) {
    return from;
  } else {
    int mid = (from + to) / 2;
    buildPresum(mid);
    if(isGood()) {
      return cautbin(from, mid);
    }else {
      return cautbin(mid+1, to);
    }
  }
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

  n = R;
  m = C;
  high = H;
  wide = W;
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= m;j++) {
      mat[i][j] = Q[i-1][j-1];
    }
  }
  return cautbin(1, R * C);
}	

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