Submission #201732

#	Time	Username	Problem	Language	Result	Execution time	Memory
201732		Leonardo_Paes	Quality Of Living (IOI10_quality)	C++17	100 / 100	3509 ms	143188 KiB

quality

#include "quality.h"

using namespace std;

const int maxn = 3e3+10;

int n, m, hh, ww, mat[maxn][maxn], b[maxn][maxn], sum[maxn][maxn];

bool check(int x){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(mat[i][j] > x) b[i][j] = 1;
            else if(mat[i][j] == x) b[i][j] = 0;
            else b[i][j] = -1;
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            sum[i][j] = b[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            if(i>=hh and j >= ww and (sum[i][j] - sum[i-hh][j] - sum[i][j-ww] + sum[i-hh][j-ww]) <= 0) return true;
        }
    }

    return false;
}

int rectangle(int r, int c, int h, int w, int a[3001][3001]) {
    n = r, m = c, hh = h, ww = w;

	for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            mat[i][j] = a[i-1][j-1];
        }
	}

	int ini = 1, fim = n*m, meio, ans = -1;

	while(ini <= fim){
        meio = (ini + fim) >> 1;

        if(check(meio)){
            fim = meio - 1;
            ans = meio;
        }
        else{
            ini = meio + 1;
        }
	}

	return ans;
}

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