Submission #1266174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266174		comgaTramAnh	Quality Of Living (IOI10_quality)	C++20	100 / 100	1143 ms	70996 KiB

quality

#include "quality.h"
int a[3001][3001];
int sum[3001][3001]; 
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  int lo = 0;
  int hi = -1; 
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      if (hi < Q[i][j]) {
        hi = Q[i][j]; 
      }
    }
  }
  int ans = -1; 
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        int value = (Q[i][j] <= mid ? 1 : -1);
        sum[i][j] = value + (i == 0 ? 0 : sum[i - 1][j]) + (j == 0 ? 0 : sum[i][j - 1]) - ((i == 0 || j == 0) ? 0 : sum[i - 1][j - 1]); 
      }
    }
    bool found = false; 
    for (int x1 = 0; x1 + H - 1 < R; x1++) {
      for (int y1 = 0; y1 + W - 1 < C; y1++) {
        int x2 = x1 + H - 1;
        int y2 = y1 + W - 1; 
        int value = sum[x2][y2] - (x1 == 0 ? 0 : sum[x1 - 1][y2]) - (y1 == 0 ? 0 : sum[x2][y1 - 1]) + ((x1 == 0 || y1 == 0) ? 0 : sum[x1 - 1][y1 - 1]);
        if (value > 0) {
          found = true; 
        }
      }
    }
    if (found == true) {
      ans = mid;
      hi = mid - 1; 
    }  
    else {
      lo = mid + 1; 
    }
  }
  return ans;
}

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