Submission #1175856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175856		nightingale	Quality Of Living (IOI10_quality)	C++20	100 / 100	875 ms	70996 KiB

quality

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

long long rectangle(int r, int c, int h, int w, int city[3001][3001]) {
    // Find min and max values for binary search
    int min_val = INT_MAX, max_val = INT_MIN;
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            min_val = min(min_val, city[i][j]);
            max_val = max(max_val, city[i][j]);
        }
    }

    int window_size = h * w;
    int median_pos = (window_size + 1) / 2;
    int lo = min_val, hi = max_val;

    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        // Build prefix sum array for elements <= mid
        int prefix[3002][3002] = {0};
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                prefix[i+1][j+1] = prefix[i+1][j] + prefix[i][j+1] - prefix[i][j] + 
                                  (city[i][j] <= mid ? 1 : 0);
            }
        }

        // Check all subrectangles
        bool possible = false;
        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 >= median_pos) {
                    possible = true;
                    break;
                }
            }
            if(possible) break;
        }

        if(possible) 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