oj.uz

Submission #733782

# Submission time Handle Problem Language Result Execution time Memory
733782 2023-05-01T09:48:39 Z penguin133 Quality Of Living (IOI10_quality) C++17
100 / 100
 1951 ms 140156 KB 
#include <bits/stdc++.h>
using namespace std;

#include "quality.h"
//#define int long long
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int lo = 1, hi = R * C, ans = lo;
	int A[R+1][C+1] = {0};
	while(lo <= hi){
		int mid = (lo + hi) >> 1;
		for(int i=1;i<=R;i++){
			for(int j=1;j<=C;j++){
				A[i][j] = (Q[i-1][j-1] <= mid ? 1 : -1);
				A[i][j] += A[i][j-1] + A[i-1][j] - A[i-1][j-1];
			}
		}
		bool f = 0;
		for(int i=H;i<=R;i++){
			for(int j=W;j<=C;j++){
				if(A[i][j] - A[i-H][j] - A[i][j-W] + A[i-H][j-W] >= 1)f = 1;
			}
		}
		if(f)ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 740 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 16 ms 2668 KB Output is correct
8 Correct 20 ms 2684 KB Output is correct
9 Correct 16 ms 2500 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 16 ms 2668 KB Output is correct
8 Correct 20 ms 2684 KB Output is correct
9 Correct 16 ms 2500 KB Output is correct
10 Correct 194 ms 18872 KB Output is correct
11 Correct 219 ms 18872 KB Output is correct
12 Correct 92 ms 11536 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 16 ms 2668 KB Output is correct
8 Correct 20 ms 2684 KB Output is correct
9 Correct 16 ms 2500 KB Output is correct
10 Correct 194 ms 18872 KB Output is correct
11 Correct 219 ms 18872 KB Output is correct
12 Correct 92 ms 11536 KB Output is correct
13 Correct 1770 ms 140156 KB Output is correct
14 Correct 1951 ms 140152 KB Output is correct
15 Correct 1470 ms 129588 KB Output is correct