Submission #536316

#	Time	Username	Problem	Language	Result	Execution time	Memory
536316		Leo121	Quality Of Living (IOI10_quality)	C++14	100 / 100	1962 ms	70820 KiB

quality

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

int acum[3005][3005];

int query(int x, int y, int _x, int _y){
    int suma = 0;
    suma = acum[_x][_y] + acum[x - 1][y - 1];
    suma-= acum[_x][y - 1];
    return suma-= acum[x - 1][_y];
}

bool probar(int cant, int n, int m, int x, int y){
    for(int i = x; i <= n; ++i){
        for(int j = y; j <= m; ++j){
            int aux = query(i - x + 1, j - y + 1, i, j);
            if(aux <= cant) return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

    int inf = 1, sup = R * C, medio, ans = 1, busco = H * W;
    busco/=2;
    while(inf <= sup){
        medio = (inf + sup) / 2;
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                if(Q[i][j] > medio) acum[i + 1][j + 1] = 1;
                else acum[i + 1][j + 1] = 0;

                acum[i + 1][j + 1] += acum[i + 1][j] + acum[i][j + 1] - acum[i][j];
            }
        }
        if(probar(busco, R, C, H, W)){
            ans = medio;
            sup = medio - 1;
        }else{
            inf = medio + 1;
        }
    }
    return ans;
}

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