Submission #1265896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265896		canhnam357	Quality Of Living (IOI10_quality)	C++20	100 / 100	1282 ms	70896 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
const int MAXN = 1e7 + 5;
const int inf = 1e18;
int pre[3001][3001] = {};
int rectangle(int n, int m, int w, int h, int a[3001][3001]) {
    int median = (w * h + 1) >> 1;
    int l = 0, r = n * m + 1;
    auto can = [&](int mid)
    {
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) pre[i][j] = (a[i][j] <= mid);
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        for (int i = w - 1; i < n; i++) for (int j = h - 1; j < m; j++)
        {
            int sum = pre[i][j] - pre[i - w][j] - pre[i][j - h] + pre[i - w][j - h];
            if (sum >= median) return true;
        }
        return false;
    };
    while (r - l > 1)
    {
        int mid = (l + r) >> 1;
        if (can(mid)) r = mid;
        else l = mid;
    }
    return r;
}

Compilation message (stderr)

quality.cpp:6:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | const int inf = 1e18;
      |                 ^~~~

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