Submission #1123451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123451		njoop	Quality Of Living (IOI10_quality)	C++17	100 / 100	2689 ms	106768 KiB

quality

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

vector<vector<int>> v;
int r, c, h, w;

bool check(int val) {
    vector<vector<int>> n(r+10, vector<int>(c+10, 0));
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            if(v[i][j] <= val) n[i+1][j+1] = 1; 
        }
    }
    for(int i=1; i<=r; i++) {
        for(int j=1; j<=c; j++) {
            n[i][j] += n[i-1][j] + n[i][j-1] - n[i-1][j-1];
        }
    }
    for(int i=h; i<=r; i++) {
        for(int j=w; j<=c; j++) {
            if(n[i][j]-n[i-h][j]-n[i][j-w]+n[i-h][j-w] > (h*w)/2) 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;
    v.assign(3010, vector<int>(3010, 0));
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            v[i][j] = Q[i][j];
        }
    }
    int lo=1, hi=r*c+1;
    while(lo < hi) {
        int mid = (lo+hi)/2;
        if(check(mid)) {
            hi = mid;
        } else {
            lo = mid+1;
        }
    }
    return lo;
}

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