Submission #536312

#	Time	Username	Problem	Language	Result	Execution time	Memory
536312		AlexRex0	Quality Of Living (IOI10_quality)	C++14	100 / 100	4362 ms	70884 KiB

quality

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

int acum[3002][3002];

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){
    bool valido = false;
    for(int j = 1; j <= m; ++j){
        for(int i = 1; i <= n; ++i){
            acum[i][j]+= acum[i - 1][j];
            if(i >= x && j >= y){
                int aux = query(i - x + 1, j - y + 1, i, j);
                if(aux <= cant){
                    valido = true;
                    break;
                }
            }
        }
    }
    return valido;
}

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];
            }
        }
        ///cout << inf << ' ' << sup <<  ' ' << medio << "\n";
        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