제출 #1296444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296444		kantaponz	삶의 질 (IOI10_quality)	C++20	100 / 100	1512 ms	106328 KiB

quality

#include <bits/stdc++.h>
using namespace std;

int R, C, H, W, A[3005][3005];
int dp[3005][3005];


int query(int i1, int j1, int i2, int j2) {
    return dp[i2][j2] - dp[i2][j1 - 1] - dp[i1 - 1][j2] + dp[i1 - 1][j1 - 1];
}

bool solve(int X) {
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = (A[i][j] < X ? 1 : -1);
            if (A[i][j] == X) dp[i][j] = 0;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + dp[i][j];
        }
    }
    for (int i = 1; i + H - 1 <= R; i++) {
        for (int j = 1; j + W - 1 <= C; j++) {
            if (query(i, j, i + H - 1, j + W - 1) >= 0) return true;
        }
    }
    return false;
}

int rectangle(int r, int c, int h, int w, int q[3001][3001]) {
    R = r;
    C = c;
    H = h;
    W = w;
    ///*
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            A[i][j] = q[i - 1][j - 1];
        }
    }//*/

    int left = 1, right = R * C;
    int ans = 1e9;
    ///*
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (solve(mid)) {
            right = mid - 1;
            ans = min(ans, mid);
        } else {
            left = mid + 1;
        }
    }//*/
    return ans;
}

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