Submission #1216357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216357		xueyic	Quality Of Living (IOI10_quality)	C++20	0 / 100	1 ms	832 KiB

quality

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int RR = 3100;
const int CC = 3100;

ll prefixMat[RR][CC];
ll prefixRows[RR][CC];
ll prefixCols[CC][RR];

bool cando(int k, int R, int C, int H, int W, int Q[3001][3001]) {
    // make prefix Rows
    // 0 of Q is 1 of prefixRows
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            int I = i + 1;
            int J = j + 1;
            prefixRows[I][J] = prefixRows[I][J - 1];
            if (Q[i][j] < k) {
                prefixRows[I][J] -= 1;
            } else if (Q[i][j] > k) {
                prefixRows[I][J] += 1;
            }
        }
    }

    for (int j = 0; j < C; j++) {
        for (int i = 0; i < R; i++) {
            int I = i + 1;
            int J = j + 1;
            prefixCols[J][I] = prefixCols[J][I - 1];
            if (Q[i][j] < k) {
                prefixCols[J][I] -= 1;
            } else if (Q[i][j] > k) {
                prefixCols[J][I] += 1;
            }
        }
    }

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            prefixMat[i][j] = prefixMat[i][j-1] + prefixCols[j][i];
        }
    }

    for (int i = 1; i + H - 1 <= R; i++) {
        for (int j = 1; j + W - 1 <= C; j++) {
            if (prefixMat[i + H - 1][j + W - 1] - prefixMat[i + H - 1][j - 1] - prefixMat[i - 1][j + W - 1] + prefixMat[i-1][j-1] >= 0) {
                return true;
            }
        }
    }

    return false;
}

int rectangle(int R,int C,int H,int W,int Q[3001][3001]) {
    int lo = 1;
    int hi = R * C;
    int best = 1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (cando(mid, R, C, H, W, Q)) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return best;
}

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