Submission #841684

#	Time	Username	Problem	Language	Result	Execution time	Memory
841684		asdfgrace	Quality Of Living (IOI10_quality)	C++17	100 / 100	2400 ms	140916 KiB

quality

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

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  int lo = 1, hi = R * C;
  auto ok = [&](int x) -> bool {
    vector<vector<int>> v(R, vector<int>(C, 0));
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        if (Q[i][j] <= x) {
          v[i][j] = 1;
        }
      }
    }
    for (int i = 0; i < R; ++i) {
      for (int j = 1; j < C; ++j) {
        v[i][j] += v[i][j - 1];
      }
    }
    for (int i = 1; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        v[i][j] += v[i - 1][j];
      }
    }
    for (int i = 0; i < R - H + 1; ++i) {
      for (int j = 0; j < C - W + 1; ++j) {
        int a = ((i > 0 && j > 0) ? v[i - 1][j - 1] : 0);
        int b = (i > 0 ? v[i - 1][j + W - 1] : 0);
        int c = (j > 0 ? v[i + H - 1][j - 1] : 0);
        int d = v[i + H - 1][j + W - 1];
        if (a + d - b - c > H * W / 2) return true;
      }
    }
    return false;
  };
  while (hi > lo) {
    int m = (lo + hi) / 2;
    if (ok(m)) {
      hi = m;
    } else {
      lo = m + 1;
    }
  }
  return hi;
}

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