Submission #1103529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103529		nyalia	Quality Of Living (IOI10_quality)	C++17	100 / 100	1175 ms	140116 KiB

quality

// for some 0, 0 to row, col, prefix stores num elements less than/eq val.
// if num elements = H*W/2 + 1 then it works
int prefix[3000][3000];
void init_prefix(int val, int R, int C, int Q[3001][3001]) {
    prefix[0][0] = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            prefix[i + 1][j + 1] = Q[i][j] <= val;
        }
    }

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            prefix[i][j] += prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
        }
    }

}

// check if median can be median
int f(int median, int H, int W, int R, int C, int Q[30001][3001]) {
    init_prefix(median, R, C, Q);
    int vals_before = (H * W) / 2 + 1;

    for (int i = 0; i <= R - H; i++) {
        for (int j = 0; j <= C - W; j++) {
            int count = prefix[i + H][j + W] - prefix[i][j + W] - prefix[i + H][j] + prefix[i][j];
            if (count >= vals_before) return true;
        }
    }

    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int best_quality = 0;

    // binary search for min med
    int lo = 1;
    int hi = R * C;
    // Range [lo, hi];
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (f(mid, H, W, R, C, Q)) {
            best_quality = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

	return best_quality;
}

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