Submission #492094

#	Time	Username	Problem	Language	Result	Execution time	Memory
492094		Alexandruabcde	Quality Of Living (IOI10_quality)	C++14	100 / 100	1674 ms	210816 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 3005;
int N, M, X, Y;
int mat[NMAX][NMAX];

int mare[NMAX][NMAX];
int mic[NMAX][NMAX];

bool Check (int val) {
    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j ) {
            mare[i][j] = mare[i-1][j] + mare[i][j-1] - mare[i-1][j-1] + (mat[i][j] > val);
            mic[i][j] = mic[i-1][j] + mic[i][j-1] - mic[i-1][j-1] + (mat[i][j] < val);
        }

    for (int i = X; i <= N; ++ i ) {
        for (int j = Y; j <= M; ++ j ) {
            int cntMare = mare[i][j] - mare[i-X][j] - mare[i][j-Y] + mare[i-X][j-Y];
            int cntMic = mic[i][j] - mic[i-X][j] - mic[i][j-Y] + mic[i-X][j-Y];

            if (cntMic >= cntMare) return 1;
        }
    }

    return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    N = R, M = C, X = H, Y = W;

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j )
            mat[i][j] = Q[i-1][j-1];

    int st = 1, dr = R * C + 1;
    int ans = 0;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (Check(mij)) {
            dr = mij-1;
            ans = mij;
        }
        else st = mij + 1;
    }

    return ans;
}

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