Submission #512658

#	Time	Username	Problem	Language	Result	Execution time	Memory
512658		Markomafko972	Quality Of Living (IOI10_quality)	C++14	100 / 100	2238 ms	70924 KiB

quality

#include "quality.h"

int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
    int p[3005][3005];

    for (int i = n-1; i >= 0; i--) {
        for (int j = m-1; j >= 0; j--) {
            a[i+1][j+1] = a[i][j];
        }
    }

	int lo = 1, hi = n*m;
    while (lo < hi) {
        int mid = (lo + hi) / 2;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                p[i][j] = 0;
                if (a[i][j] <= mid) p[i][j] = 1;
                p[i][j] += p[i-1][j]+p[i][j-1]-p[i-1][j-1];
            }
        }

        int da = 0;
        for (int i = h; i <= n; i++) {
            for (int j = w; j <= m; j++) {
                if (p[i][j]-p[i-h][j]-p[i][j-w]+p[i-h][j-w] > (h*w)/2) {
                    da = 1;
                    break;
                }
            }

            if (da) break;
        }

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