oj.uz

Submission #201732

# Submission time Handle Problem Language Result Execution time Memory
201732 2020-02-11T21:01:14 Z Leonardo_Paes Quality Of Living (IOI10_quality) C++17
100 / 100
 3509 ms 143188 KB 
#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.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 764 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 8 ms 2168 KB Output is correct
5 Correct 8 ms 2092 KB Output is correct
6 Correct 8 ms 2168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 764 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 8 ms 2168 KB Output is correct
5 Correct 8 ms 2092 KB Output is correct
6 Correct 8 ms 2168 KB Output is correct
7 Correct 34 ms 7160 KB Output is correct
8 Correct 35 ms 7160 KB Output is correct
9 Correct 30 ms 6904 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 764 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 8 ms 2168 KB Output is correct
5 Correct 8 ms 2092 KB Output is correct
6 Correct 8 ms 2168 KB Output is correct
7 Correct 34 ms 7160 KB Output is correct
8 Correct 35 ms 7160 KB Output is correct
9 Correct 30 ms 6904 KB Output is correct
10 Correct 364 ms 38776 KB Output is correct
11 Correct 368 ms 38904 KB Output is correct
12 Correct 178 ms 27516 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 764 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 8 ms 2168 KB Output is correct
5 Correct 8 ms 2092 KB Output is correct
6 Correct 8 ms 2168 KB Output is correct
7 Correct 34 ms 7160 KB Output is correct
8 Correct 35 ms 7160 KB Output is correct
9 Correct 30 ms 6904 KB Output is correct
10 Correct 364 ms 38776 KB Output is correct
11 Correct 368 ms 38904 KB Output is correct
12 Correct 178 ms 27516 KB Output is correct
13 Correct 3509 ms 143188 KB Output is correct
14 Correct 3503 ms 143132 KB Output is correct
15 Correct 3124 ms 142712 KB Output is correct