oj.uz

Submission #536312

# Submission time Handle Problem Language Result Execution time Memory
536312 2022-03-12T20:14:37 Z AlexRex0 Quality Of Living (IOI10_quality) C++14
100 / 100
 4362 ms 70884 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 20 ms 3340 KB Output is correct
8 Correct 20 ms 3420 KB Output is correct
9 Correct 18 ms 3356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 20 ms 3340 KB Output is correct
8 Correct 20 ms 3420 KB Output is correct
9 Correct 18 ms 3356 KB Output is correct
10 Correct 298 ms 16132 KB Output is correct
11 Correct 278 ms 16136 KB Output is correct
12 Correct 134 ms 12208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 20 ms 3340 KB Output is correct
8 Correct 20 ms 3420 KB Output is correct
9 Correct 18 ms 3356 KB Output is correct
10 Correct 298 ms 16132 KB Output is correct
11 Correct 278 ms 16136 KB Output is correct
12 Correct 134 ms 12208 KB Output is correct
13 Correct 4362 ms 70884 KB Output is correct
14 Correct 3664 ms 70776 KB Output is correct
15 Correct 4113 ms 70844 KB Output is correct