제출 #1039945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039945		ArthuroWich	Quality Of Living (IOI10_quality)	C++17	100 / 100	1052 ms	106124 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int n, int m, int h, int w, int q[3001][3001]) {
    int l = 1, r = n*m;
    while(l < r) {
        int mi = (l+r)/2;
        vector<vector<int>> pref(n+1, vector<int>(m+1, 0));
        bool f = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(q[i-1][j-1]<=mi);
                if (i-h >= 0 && j-w >= 0) {
                    if (pref[i][j]-pref[i][j-w]-pref[i-h][j]+pref[i-h][j-w] > h*w/2) {
                        f = 1;
                    }
                }
            }
        }
        if (f) {
            r = mi;
        } else {
            l = mi+1;
        }
    }
    return l;
}

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