oj.uz

Submission #357610

# Submission time Handle Problem Language Result Execution time Memory
357610 2021-01-24T08:57:01 Z Mefarnis Quality Of Living (IOI10_quality) C++14
100 / 100
 2218 ms 140296 KB 
#include <bits/stdc++.h>
#include "quality.h"
#include "grader.h"
#define maxn 3001
using namespace std;

int sum[maxn][maxn];

int rectangle(int n, int m, int h, int w, int ar[3001][3001]) {
	int N = n*m , ans = -1;
	int l = 1 , r = N;
	while(l <= r) {
		int mid = (l+r) >> 1;
		memset(sum,0,sizeof(sum));
		for( int i = 1 ; i <= n ; i++ )
			for( int j = 1 ; j <= m ; j++ ) {
				int add = (ar[i-1][j-1] <= mid) ? +1 : -1;
				sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + add;
			}
		bool ok = false;
		for( int row = h ; row <= n ; row++ )
			for( int col = w ; col <= m ; col++ ) {
				int total = sum[row][col] - sum[row-h][col] - sum[row][col-w] + sum[row-h][col-w];
				if(total > 0)
					ok = true;
			}
		if(ok)
			ans = mid , r = mid-1;
		else
			l = mid+1;
	}
	return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 35748 KB Output is correct
2 Correct 64 ms 35692 KB Output is correct
3 Correct 63 ms 35692 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 35748 KB Output is correct
2 Correct 64 ms 35692 KB Output is correct
3 Correct 63 ms 35692 KB Output is correct
4 Correct 81 ms 36112 KB Output is correct
5 Correct 76 ms 36108 KB Output is correct
6 Correct 84 ms 36076 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 35748 KB Output is correct
2 Correct 64 ms 35692 KB Output is correct
3 Correct 63 ms 35692 KB Output is correct
4 Correct 81 ms 36112 KB Output is correct
5 Correct 76 ms 36108 KB Output is correct
6 Correct 84 ms 36076 KB Output is correct
7 Correct 116 ms 37704 KB Output is correct
8 Correct 109 ms 37740 KB Output is correct
9 Correct 106 ms 37620 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 35748 KB Output is correct
2 Correct 64 ms 35692 KB Output is correct
3 Correct 63 ms 35692 KB Output is correct
4 Correct 81 ms 36112 KB Output is correct
5 Correct 76 ms 36108 KB Output is correct
6 Correct 84 ms 36076 KB Output is correct
7 Correct 116 ms 37704 KB Output is correct
8 Correct 109 ms 37740 KB Output is correct
9 Correct 106 ms 37620 KB Output is correct
10 Correct 355 ms 50232 KB Output is correct
11 Correct 332 ms 50192 KB Output is correct
12 Correct 220 ms 44920 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 35748 KB Output is correct
2 Correct 64 ms 35692 KB Output is correct
3 Correct 63 ms 35692 KB Output is correct
4 Correct 81 ms 36112 KB Output is correct
5 Correct 76 ms 36108 KB Output is correct
6 Correct 84 ms 36076 KB Output is correct
7 Correct 116 ms 37704 KB Output is correct
8 Correct 109 ms 37740 KB Output is correct
9 Correct 106 ms 37620 KB Output is correct
10 Correct 355 ms 50232 KB Output is correct
11 Correct 332 ms 50192 KB Output is correct
12 Correct 220 ms 44920 KB Output is correct
13 Correct 2218 ms 140296 KB Output is correct
14 Correct 2175 ms 140252 KB Output is correct
15 Correct 2045 ms 133320 KB Output is correct