Submission #595777

#	Time	Username	Problem	Language	Result	Execution time	Memory
595777		snasibov05	Quality Of Living (IOI10_quality)	C++14	100 / 100	2394 ms	72952 KiB

quality

#include "quality.h"
#include "bits/stdc++.h"

using namespace std;

bool check(int k, int r, int c, int h, int w, int q[3001][3001]){

    vector<vector<int>> cntp(r, vector<int>(c));
    for (int i = 0; i < r; ++i){
        for (int j = 0; j < c; ++j){
            if (i != 0) cntp[i][j] += cntp[i-1][j];
            if (j != 0) cntp[i][j] += cntp[i][j-1];
            if (i != 0 && j != 0) cntp[i][j] -= cntp[i-1][j-1];
            cntp[i][j] += q[i][j] <= k;
        }
    }

    for (int i = h-1; i < r; ++i){
        for (int j = w-1; j < c; ++j){
            int cnt = cntp[i][j];
            if (i != h-1) cnt -= cntp[i - h][j];
            if (j != w-1) cnt -= cntp[i][j - w];
            if (i != h-1 && j != w-1) cnt += cntp[i - h][j - w];
            if (cnt > h * w / 2) return true;
        }
    }

    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

    int l = 1, r = R*C;
    int bst = 0;
    while (l <= r){
        int mid = (l + r) / 2;
        if (check(mid, R, C, H, W, Q)) bst = mid, r = mid - 1;
        else l = mid + 1;
    }

    return bst;

}

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