Submission #1263028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263028		kunzaZa183	Quality Of Living (IOI10_quality)	C++20	100 / 100	1803 ms	106368 KiB

quality

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

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  vector<vector<int>> vvi(R + 1, vector<int>(C + 1));
  auto helper = vvi;
  for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++)
      vvi[i + 1][j + 1] = Q[i][j];

  int l = 1, r = R * C;

  while (l < r) {
    int mid = (l + r) / 2;

    helper.assign(R + 1, vector<int>(C + 1));

    for (int i = 1; i <= R; i++) {
      for (int j = 1; j <= C; j++) {
        if (vvi[i][j] <= mid)
          helper[i][j] = 1;
        helper[i][j] +=
            helper[i - 1][j] + helper[i][j - 1] - helper[i - 1][j - 1];
      }
    }

    // cout << mid << "\n";
    // for (auto a : helper) {
    //   for (auto b : a)
    //     cout << b << " ";
    //   cout << "\n";
    // }

    int maxi = 0;
    for (int i = 1; i <= R; i++) {
      for (int j = 1; j <= C; j++) {
        int res = helper[min(R, i + H - 1)][min(C, j + W - 1)] -
                  helper[min(R, i + H - 1)][j - 1] -
                  helper[i - 1][min(C, j + W - 1)] + helper[i - 1][j - 1];
        // cout << i << " " << j << " " << res << "\n";
        maxi = max(maxi, res);
      }
    }
    // cout << maxi << "\n";

    if (maxi >= (H * W) / 2 + 1) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  return l;
}

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