oj.uz

Submission #366592

# Submission time Handle Problem Language Result Execution time Memory
366592 2021-02-14T17:59:17 Z kostia244 Quality Of Living (IOI10_quality) C++17
100 / 100
 2664 ms 140560 KB 
#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int Q[3001][3001];
int rectangle(int R, int C, int H, int W, int tmp[3001][3001]) {
	auto can = [&](int x) {
		for(int it = 0; it < 3; it++)
		for(int i = 0; i < R; i++)
			for(int j = 0; j < C; j++) {
				if(it == 0) Q[i][j] = tmp[i][j] >= x ? -1 : 1;
				if(it == 1 && i) Q[i][j] += Q[i-1][j];
				if(it == 2 && j) Q[i][j] += Q[i][j-1];
			}
		for(int i = H-1; i < R; i++)
			for(int j = W-1; j < C; j++) {
				int res = Q[i][j];
				if(i-H>=0) res -= Q[i-H][j];
				if(j-W>=0) res -= Q[i][j-W];
				if(i-H>=0&&j-W>=0) res += Q[i-H][j-W];
				//cout << i << " " << j << " " << res << endl;
				if(res > 0) return 1;
			}
		return 0;
	};
	int ans = -1;
	for(int i = 1<<30; i>>=1;)
		ans += i*!can(ans+i);
	return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 1260 KB Output is correct
5 Correct 4 ms 1260 KB Output is correct
6 Correct 4 ms 1260 KB Output is correct
7 Correct 28 ms 3948 KB Output is correct
8 Correct 28 ms 3948 KB Output is correct
9 Correct 26 ms 3820 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 1260 KB Output is correct
5 Correct 4 ms 1260 KB Output is correct
6 Correct 4 ms 1260 KB Output is correct
7 Correct 28 ms 3948 KB Output is correct
8 Correct 28 ms 3948 KB Output is correct
9 Correct 26 ms 3820 KB Output is correct
10 Correct 314 ms 22868 KB Output is correct
11 Correct 309 ms 22892 KB Output is correct
12 Correct 164 ms 15596 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 1260 KB Output is correct
5 Correct 4 ms 1260 KB Output is correct
6 Correct 4 ms 1260 KB Output is correct
7 Correct 28 ms 3948 KB Output is correct
8 Correct 28 ms 3948 KB Output is correct
9 Correct 26 ms 3820 KB Output is correct
10 Correct 314 ms 22868 KB Output is correct
11 Correct 309 ms 22892 KB Output is correct
12 Correct 164 ms 15596 KB Output is correct
13 Correct 2664 ms 140560 KB Output is correct
14 Correct 2645 ms 140360 KB Output is correct
15 Correct 2458 ms 133216 KB Output is correct