Submission #791728

#	Time	Username	Problem	Language	Result	Execution time	Memory
791728		elazarkoren	Quality Of Living (IOI10_quality)	C++17	100 / 100	1212 ms	175488 KiB

quality

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 3005;
int pre_sum[MAX_N][MAX_N];
int a[MAX_N][MAX_N];

// int Sum(int x1, int y1, int x2, int y2) {
//     return pre_sum[x2][y2] - pre_sum[x1 - 1][y2] - pre_sum[x2][y1 - 1] + pre_sum[x1 - 1][y1 - 1];
// }

int r, c, h, w, median;

int Ok(int x) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            pre_sum[i][j + 1] = pre_sum[i][j] + (a[i][j] > x);
            // pre_sum[i + 1][j + 1] = (a[i][j] > x) + pre_sum[i][j + 1] + pre_sum[i + 1][j] - pre_sum[i][j];
        }
    }
    vi vals(c - w + 1);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) vals[0] += a[i][j] > x;
    }
    for (int i = 0; i < h; i++) {
        for (int j = 1; j <= c - w; j++) {
            vals[j] += (a[i][j + w - 1] > x) - (a[i][j - 1] > x);
        }
    }
    for (int j = 1; j <= c - w; j++) {
        vals[j] += vals[j - 1];
    }
    if (*min_element(all(vals)) <= median) return true;
    for (int i = 1; i <= r - h; i++) {
        for (int j = 0; j <= c - w; j++) {
            vals[j] += pre_sum[i + h - 1][j + w] - pre_sum[i + h - 1][j];
            vals[j] -= pre_sum[i - 1][j + w] - pre_sum[i - 1][j];
        }
        if (*min_element(all(vals)) <= median) return true;
    }
    return false;

    // for (int i = 1; i <= r - h + 1; i++) {
    //     for (int j = 1; j <= c - w + 1; j++) {
    //         // int x = Sum(i, j, i + h - 1, j + w - 1);
    //         if (x <= median) {
    //             return true;
    //         }
    //     }
    // }
    // return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    r = R, c = C, h = H, w = W;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) a[i][j] = Q[i][j];
    }
    median = h * w / 2;
    int begin = 1, end = r * c, mid;
    while (begin < end) {
        mid = (begin + end) >> 1;
        if (Ok(mid)) end = mid;
        else begin = mid + 1;
    }
    return end;
}

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