Submission #1110980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110980		Zflop	Quality Of Living (IOI10_quality)	C++14	100 / 100	2080 ms	140304 KiB

quality

#include <bits/stdc++.h>
using namespace std;
int sum[3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int l = 1,r = R * C;
    int ans = R * C;

    auto get = [&] (int i,int j) {
        if (i + 1 < H) return -1;
        if (j + 1 < W) return -1;
        int a = sum[i][j];
        if (i - H >= 0) a -= sum[i - H][j];
        if (j - W >= 0) a -= sum[i][j - W];
        if (i - H >= 0 && j - W >= 0) a += sum[i - H][j - W];
        return a;
    };

    auto work = [&](int x) {
        for (int i = 0; i < R;++i)
            for (int j = 0; j < C;++j)
                sum[i][j] = 0;
        for (int i = 0; i < R;++i)
            for (int j = 0; j < C;++j) {
                if (Q[i][j] > x) --sum[i][j];
                if (Q[i][j] < x) ++sum[i][j];
                if (i) sum[i][j] += sum[i - 1][j];
                if (j) sum[i][j] += sum[i][j - 1];
                if (i && j) sum[i][j] -= sum[i - 1][j - 1];
            }
        for (int i = 0; i < R;++i)
            for (int j = 0; j < C;++j)
                if (get(i,j) >= 0)
                    return true;
        return false;
    };

    while (l <= r) {
        int mid = (l + r) / 2;
        if (work(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

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