Submission #1041666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041666		onbert	Quality Of Living (IOI10_quality)	C++17	100 / 100	864 ms	175700 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005, maxN = 9e6 + 5;
int n, m, h, w, target;
int a[maxn][maxn], sum[maxn][maxn];

bool ok(int x) {
    for (int i=0;i<=n;i++) sum[i][0] = 0;
    for (int i=0;i<=m;i++) sum[0][i] = 0;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (a[i][j]<=x);
    }
    bool ans = false;
    for (int i=h;i<=n;i++) for (int j=w;j<=m;j++) {
        ans |= (sum[i][j] - sum[i-h][j] - sum[i][j-w] + sum[i-h][j-w] >= target);
    }
    return ans;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    n = R, m = C, h = H, w = W, target = H*W/2+1;
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j] = Q[i-1][j-1];
    int l = 1, r = R * C;
    while (l<r) {
        int mid = (l+r)/2;
        if (ok(mid)) r = mid;
        else l = mid+1;
    }
    return l;
}

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