Submission #820130

#	Time	Username	Problem	Language	Result	Execution time	Memory
820130		WLZ	Quality Of Living (IOI10_quality)	C++17	60 / 100	5043 ms	62044 KiB

quality

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

int st[3001][3001];

void update(int i1, int j1, int i2, int j2, int v) {
  for (int i = i1; i <= i2; i++) for (int j = j1; j <= j2; j++) st[i][j] += v;
}

int query(int i1, int j1, int i2, int j2) {
  int ans = -1;
  for (int i = i1; i <= i2; i++) for (int j = j1; j <= j2; j++) ans = max(ans, st[i][j]);
  return ans;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  vector< tuple<int, int, int> > v;
  for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) v.emplace_back(Q[i][j], i, j);
  sort(v.begin(), v.end());
  memset(st, 0, sizeof st);
  for (auto &p : v) {
    int x = get<0>(p), i = get<1>(p), j = get<2>(p);
    update(max(0, i - H + 1), max(0, j - W + 1), min(i, R - H), min(j, C - W), +1);
    if (query(max(0, i - H + 1), max(0, j - W + 1), i, j) == (H * W + 1) / 2) return x;
  }
	return -1;
}

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