Submission #1212351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212351		totoro	Quality Of Living (IOI10_quality)	C++20	100 / 100	1172 ms	71016 KiB

quality

#include "quality.h"

#include <iostream>
#include <vector>

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int lo = 1, hi = R * C;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        std::vector<std::vector<int>> prefixsum(R + 1, std::vector<int>(C + 1));
        bool ok = false;
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                prefixsum[i + 1][j + 1] = prefixsum[i][j + 1] + prefixsum[i + 1][j] + (Q[i][j] > mid) - prefixsum[i][j];
                // std::cout << "prefixsum[" << i + 1 << "][" << j + 1 << "]=" << prefixsum[i + 1][j + 1] << '\n';
                if (i + 1 >= H && j + 1 >= W) {
                    int val = prefixsum[i + 1][j + 1] + prefixsum[i + 1 - H][j + 1 - W] - prefixsum[i + 1 - H][j + 1] - prefixsum[i + 1][j + 1 - W];
                    // std::cout << "for mid=" << mid << " for i=" << i << " and j=" << j << " val is " << val << '\n';
                    ok |= (val <= H * W / 2);
                }
            }
        }
        if (ok) {
            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