oj.uz

Submission #441720

# Submission time Handle Problem Language Result Execution time Memory
441720 2021-07-05T21:48:54 Z dutch Quality Of Living (IOI10_quality) C++17
100 / 100
 1949 ms 140200 KB 
#include <bits/stdc++.h>
using namespace std;
#include "quality.h"

const int LIM = 3000;

int g[LIM+1][LIM+1];

int rectangle(int r, int c, int h, int w, int q[LIM+1][LIM+1]){
	int low = 1, high = r*c;
	while(low < high){
		int mid = (low + high) / 2;

		bool ok = 0;

		for(int i=0; i<r; ++i){
			for(int j=0; j<c; ++j){
				g[i+1][j+1] = q[i][j] <= mid ? 1 : -1;
				g[i+1][j+1] += g[i][j+1] + g[i+1][j] - g[i][j];
				if(i+1>=h && j+1>=w && g[i+1][j+1] + g[i+1-h][j+1-w]
					- g[i+1-h][j+1] - g[i+1][j+1-w] > 0) ok = 1;
			}
		}

		if(ok) high = mid;
		else low = mid + 1;
	}
	return low;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 17 ms 3880 KB Output is correct
8 Correct 17 ms 3920 KB Output is correct
9 Correct 16 ms 3832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 17 ms 3880 KB Output is correct
8 Correct 17 ms 3920 KB Output is correct
9 Correct 16 ms 3832 KB Output is correct
10 Correct 210 ms 22764 KB Output is correct
11 Correct 209 ms 22864 KB Output is correct
12 Correct 107 ms 15516 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 17 ms 3880 KB Output is correct
8 Correct 17 ms 3920 KB Output is correct
9 Correct 16 ms 3832 KB Output is correct
10 Correct 210 ms 22764 KB Output is correct
11 Correct 209 ms 22864 KB Output is correct
12 Correct 107 ms 15516 KB Output is correct
13 Correct 1949 ms 140200 KB Output is correct
14 Correct 1917 ms 140188 KB Output is correct
15 Correct 1769 ms 133120 KB Output is correct