Submission #1164382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164382		julia_08	Quality Of Living (IOI10_quality)	C++20	100 / 100	1342 ms	71000 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e3 + 10;

int s[MAXN][MAXN];

bool in(int x, int y, int R, int C){
  return x >= 0 && x < R && y >= 0 && y < C;
}

bool check(int R, int C, int H, int W, int Q[3001][3001], int x){

  for(int i=0; i<R; i++){
    for(int j=0; j<C; j++){

      s[i][j] = (Q[i][j] <= x);

      if(i > 0) s[i][j] += s[i - 1][j];
      if(j > 0) s[i][j] += s[i][j - 1];
      if(i > 0 && j > 0) s[i][j] -= s[i - 1][j - 1];

    }
  }

  for(int i=0; i<R; i++){
    for(int j=0; j<C; j++){

      int x_1 = i, y_1 = j, x_2 = i + H - 1, y_2 = j + W - 1;

      if(in(x_1, y_1, R, C) && in(x_1, y_2, R, C) && in(x_2, y_1, R, C) && in(x_2, y_2, R, C)){

        int sum = s[x_2][y_2];

        if(x_1 > 0) sum -= s[x_1 - 1][y_2];
        if(y_1 > 0) sum -= s[x_2][y_1 - 1];
        if(x_1 > 0 && y_1 > 0) sum += s[x_1 - 1][y_1 - 1];

        if(sum >= (H * W + 1) / 2) return true;

      }

    }
  }

  return false;

}

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

  int l = 1, r = R * C;

  while(l < r){

    int m = l + (r - l) / 2;

    if(check(R, C, H, W, Q, m)) r = m;
    else l = m + 1;

  }

  return r;
}

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