제출 #1175854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175854		nightingale	Quality Of Living (IOI10_quality)	C++20	60 / 100	5096 ms	20084 KiB

quality

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

long long rectangle(int r, int c, int h, int w, int city[3001][3001]) 
{
    long long best = LLONG_MAX;
    int window_size = h * w;
    int median_pos = (window_size + 1) / 2 - 1;

    // For each starting row
    for(int i = 0; i <= r-h; i++) {
        // Use multiset to maintain sorted window values
        multiset<int> window;
        
        // Initialize first window of this row
        for(int k = 0; k < h; k++) {
            for(int m = 0; m < w; m++) {
                window.insert(city[i+k][m]);
            }
        }
        
        // Get median of first window
        auto it = window.begin();
        advance(it, median_pos);
        best = min(best, (long long)*it);

        // Slide window horizontally
        for(int j = 1; j <= c-w; j++) {
            // Remove leftmost column
            for(int k = 0; k < h; k++) {
                window.erase(window.find(city[i+k][j-1]));
            }
            // Add rightmost column
            for(int k = 0; k < h; k++) {
                window.insert(city[i+k][j+w-1]);
            }
            // Get new median
            it = window.begin();
            advance(it, median_pos);
            best = min(best, (long long)*it);
        }
    }
    
    return best;
}

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