Submission #512140

#	Time	Username	Problem	Language	Result	Execution time	Memory
512140		600Mihnea	Quality Of Living (IOI10_quality)	C++17	100 / 100	1992 ms	139980 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

int a[3001][3001];

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

int rectangle(int n, int m, int h, int w, int matrix[3001][3001]) {
  /// for the example the solution is 9

  int low = 1, high = n * m, sol = -1;
  while (low <= high) {
    int want = (low + high) / 2;
    bool ok = 0;
    for (int i = 1; i <= n; i++) {
      int current = 0;
      for (int j = 1; j <= m; j++) {
        if (matrix[i - 1][j - 1] > want) {
          a[i][j] = -1;
        } else {
          if (matrix[i - 1][j - 1] < want) {
            a[i][j] = +1;
          } else {
            a[i][j] = 0;
          }
        }
        current += a[i][j];
        a[i][j] = a[i - 1][j] + current;
      }
    }
    for (int i = 1; i + h - 1 <= n; i++) {
      for (int j = 1; j + w - 1 <= m; j++) {
        if (getsum(i, j, i + h - 1, j + w - 1) >= 0) {
          ok = 1;
        }
      }
    }
    if (ok) {
      sol = want;
      high = want - 1;
    } else {
      low = want + 1;
    }
  }
  assert(sol != -1);
  return sol;
}

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