Submission #1013008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013008		u_suck_o	Quality Of Living (IOI10_quality)	C++17	100 / 100	1540 ms	175180 KiB

quality

#include "bits/stdc++.h"
#include "quality.h"
 
using namespace std;
 
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    long long arr[R+1][C+1];
    memset(arr, 0, sizeof arr);
    
    int l = 1, r = R*C;
    while (l < r) {
        int mid = (l+r)/2;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (Q[i][j] <= mid)
                    arr[i+1][j+1] = 1;
                else
                    arr[i+1][j+1] = 0;
                arr[i+1][j+1] += arr[i+1][j] + arr[i][j+1] - arr[i][j];
            }
        }
        
        bool valid = false;
        for (int i = 1; i + H - 1<= R; i++) {
            for (int j = 1; j + W - 1<= C; j++) {
                if (arr[i+H-1][j+W-1] - arr[i+H-1][j-1] - arr[i-1][j+W-1] + arr[i-1][j-1] > H*W/2) {
                    valid = true;
                    break;
                }
            }
        }
        if (valid)
            r = mid;
        else
            l = mid+1;
    }
    return r;
}

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