Submission #1265894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265894		canhnam357	Quality Of Living (IOI10_quality)	C++20	0 / 100	0 ms	576 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 = 1; i <= n; i++) for (int j = 1; j <= m; j++) pre[i][j] = (a[i][j] <= mid);
        for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        for (int i = w; i <= n; i++) for (int j = h; 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;
}
// int a[3001][3001];
// int32_t main()
// {
//     ios_base::sync_with_stdio(false);
//     cin.tie(0);
//     int n, m, w, h;
//     cin >> n >> m >> w >> h;
//     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
//     cout << rectangle(n, m, w, h, a);
//     return 0;
// }

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: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20