Submission #440159

#	Time	Username	Problem	Language	Result	Execution time	Memory
440159		dxz05	Quality Of Living (IOI10_quality)	C++14	100 / 100	3079 ms	175332 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

int N, M, H, W, A[3001][3001];

int dp[3001][3001];

bool check(int val){
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            dp[i][j] = (A[i][j] < val ? -1 : A[i][j] == val ? 0 : 1);
            if (j) dp[i][j] += dp[i][j - 1];
        }
    }

    for (int j = 0; j < M; j++){
        for (int i = 1; i < N; i++){
            dp[i][j] += dp[i - 1][j];
        }
    }

    /*for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }*/

    for (int i = H - 1; i < N; i++){
        for (int j = W - 1; j < M; j++){
            int sum = dp[i][j];
            if (i >= H) sum -= dp[i - H][j];
            if (j >= W) sum -= dp[i][j - W];
            if (i >= H && j >= W) sum += dp[i - H][j - W];
            if (sum <= 0) return true;
        }
    }

    return false;
}

int rectangle(int _R, int _C, int _H, int _W, int _Q[3001][3001]) {
	N = _R, M = _C, H = _H, W = _W;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) A[i][j] = _Q[i][j];

    int ans = N * M;
    int l = 1, r = N * M;
    while (l <= r){
        int m = (l + r) >> 1;
        if (check(m)){
            ans = m;
            r = m - 1;
        } else l = m + 1;
    }

    return ans;
}

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