oj.uz

Submission #512660

# Submission time Handle Problem Language Result Execution time Memory
512660 2022-01-16T15:48:20 Z lovro_nidogon1 Quality Of Living (IOI10_quality) C++14
100 / 100
 2925 ms 141232 KB 
#include<bits/stdc++.h>
#include<quality.h>
#define breturn return
using namespace std;

int mat[3001][3001], r, c, h, w;
int sus[3001][3001], lo = 0, hi = 1e9, mid, exsus[3001][3001];

bool fun() {
	 for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) {
	 	if(mat[i][j] > mid) sus[i][j] = -1;
	 	else if(mat[i][j] < mid) sus[i][j] = 1;
	 	else sus[i][j] = 0;
	 }

	 for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) {
	 	exsus[i][j] = sus[i][j];
	 	if(i and j) exsus[i][j] += exsus[i - 1][j] + exsus[i][j - 1] - exsus[i - 1][j - 1];
	 	else if(i) exsus[i][j] += exsus[i - 1][j];
	 	else if(j) exsus[i][j] += exsus[i][j - 1];
    }	 	

    for(int i = h - 1; i < r; i++) for(int j = w - 1; j < c; j++) {
		int sum = exsus[i][j];
		if(i - h >= 0 and j - w >= 0) sum -= exsus[i - h][j] + exsus[i][j - w] - exsus[i - h][j - w];
		else if(i - h >= 0 ) sum -= exsus[i - h][j];
		else if(j - w >= 0) sum -= exsus[i][j - w];	 	
    	if(sum >= 0) {
    		breturn true;
			   }
	}
	breturn false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	r = R;
	c = C;
	h = H;
	w = W;
	for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) mat[i][j] = Q[i][j];
	for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) cin >> mat[i][j];
	while(hi != lo) {
		mid = (hi + lo)/2;	
		if(fun()) hi = mid;
		else lo = mid + 1;
	}
	breturn hi;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 3 ms 1996 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct
7 Correct 28 ms 6468 KB Output is correct
8 Correct 41 ms 6428 KB Output is correct
9 Correct 28 ms 6400 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 3 ms 1996 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct
7 Correct 28 ms 6468 KB Output is correct
8 Correct 41 ms 6428 KB Output is correct
9 Correct 28 ms 6400 KB Output is correct
10 Correct 329 ms 31924 KB Output is correct
11 Correct 329 ms 31932 KB Output is correct
12 Correct 173 ms 24108 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 3 ms 1996 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct
7 Correct 28 ms 6468 KB Output is correct
8 Correct 41 ms 6428 KB Output is correct
9 Correct 28 ms 6400 KB Output is correct
10 Correct 329 ms 31924 KB Output is correct
11 Correct 329 ms 31932 KB Output is correct
12 Correct 173 ms 24108 KB Output is correct
13 Correct 2925 ms 141232 KB Output is correct
14 Correct 2876 ms 141212 KB Output is correct
15 Correct 2611 ms 141224 KB Output is correct