Submission #335588

#	Time	Username	Problem	Language	Result	Execution time	Memory
335588		Joshc	Quality Of Living (IOI10_quality)	C++98	100 / 100	2544 ms	96096 KiB

quality

#include <cstdio>
#include <algorithm>
using namespace std;

int r, c, h, w, prefix[3001][3001];

void update(int i, int j, int delta) {
  prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + delta;
}

int query(int x1, int y1, int x2, int y2) {
  return prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];
}

bool work(int x, int grid[3001][3001], int r, int c, int h, int w) {
  for (int i=0; i<=r; i++) {
    prefix[i][0] = 0;
  }
  for (int j=0; j<=c; j++) {
    prefix[0][j] = 0;
  }
  for (int i=1; i<=r; i++) {
    for (int j=1; j<=c; j++) {
      if (grid[i-1][j-1]>x) {
        update(i, j, -1);
      } else if (grid[i-1][j-1]==x) {
        update(i, j, 0);
      } else {
        update(i, j, 1);
      }
    }
  }
  for (int i=1; i<=r-h+1; i++) {
    for (int j=1; j<=c-w+1; j++) {
      if (query(i, j, i+h-1, j+w-1) >= 0) return true;
    }
  }
  return false;
}

int rectangle(int r, int c, int h, int w, int grid[3001][3001]) {
  int low=1, high=r*c, mid;
  while (low != high) {
    mid = (low+high)>>1;
    if (!work(mid, grid, r, c, h, w)) {
      low = mid+1;
    } else {
      high = mid;
    }
  }
  return low;
}

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