Submission #311613

#	Time	Username	Problem	Language	Result	Execution time	Memory
311613		ipaljak	Quality Of Living (IOI10_quality)	C++14	100 / 100	2684 ms	140408 KiB

quality

#include "quality.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3005;

int r, c;
int mat[MAXN][MAXN];

int sum(int r1, int c1, int r2, int c2) {
  return mat[r2][c2] - mat[r1 - 1][c2] - mat[r2][c1 - 1] + mat[r1 - 1][c1 - 1];
}

bool check(int h, int w) {
  for (int i = 1; i <= r; ++i)
    for (int j = 1; j <= c; ++j)
      mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];

  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      if (i + h - 1 > r || j + w - 1 > c) continue;
      if (sum(i, j, i + h - 1, j + w - 1) > h * w / 2) return true;
    }
  }

  return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  r = R; c = C;
  int lo = 1, hi = R * C;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j)
        mat[i + 1][j + 1] = Q[i][j] <= mid;
    if (check(H, W)) hi = mid; else lo = mid + 1;
  }

  return lo;
}

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