Submission #597261

#	Time	Username	Problem	Language	Result	Execution time	Memory
597261		proma	Quality Of Living (IOI10_quality)	C++17	100 / 100	2117 ms	107436 KiB

quality

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

using namespace std;

int g[3001][3001];
int s[3001][3001];

bool check(int x, int R, int C, int H, int W, int Q[3001][3001]) {
    for (int i = 0; i < R; i ++) {
        for (int j = 0; j < C; j ++) {
            if (Q[i][j] < x) g[i+1][j+1] = -1;
            if (Q[i][j] == x) g[i+1][j+1] = 0;
            if (Q[i][j] > x) g[i+1][j+1] = 1;
            s[i+1][j+1] = g[i+1][j+1] + s[i][j+1] + s[i+1][j] - s[i][j];
        }
    }
    for (int i = H; i <= R; i ++) {
        for (int j = W; j <= C; j ++) {
            if (s[i][j] - s[i-H][j] - s[i][j-W] + s[i-H][j-W] <= 0) return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int l = 1, r = R*C;
    while (l < r) {
        int m = (l + r) / 2;
        if (check(m, R, C, H, W, Q)) {
            r = m;
        }
        else {
            l = m + 1;
        }
    }
    return l;
}

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