oj.uz

Submission #531452

# Submission time Handle Problem Language Result Execution time Memory
531452 2022-02-28T17:52:41 Z AdamGS Quality Of Living (IOI10_quality) C++17
100 / 100
 2208 ms 140320 KB 
#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e3+7;
int sum[LIM][LIM];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int p=1, k=R*C;
	while(p<k) {
		int sr=(p+k)/2;
		rep(i, R) rep(j, C) {
			sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[i][j];
			if(Q[i][j]<=sr) ++sum[i+1][j+1];
		}
		int ma=0;
		for(int i=H; i<=R; ++i) for(int j=W; j<=C; ++j) {
			ma=max(ma, sum[i][j]-sum[i-H][j]-sum[i][j-W]+sum[i-H][j-W]);
		}
		if(ma<(H*W+1)/2) p=sr+1; else k=sr;
	}
	return p;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 540 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1192 KB Output is correct
6 Correct 3 ms 1228 KB Output is correct
7 Correct 21 ms 3808 KB Output is correct
8 Correct 18 ms 3884 KB Output is correct
9 Correct 16 ms 3712 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 540 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1192 KB Output is correct
6 Correct 3 ms 1228 KB Output is correct
7 Correct 21 ms 3808 KB Output is correct
8 Correct 18 ms 3884 KB Output is correct
9 Correct 16 ms 3712 KB Output is correct
10 Correct 217 ms 22780 KB Output is correct
11 Correct 219 ms 22868 KB Output is correct
12 Correct 117 ms 15396 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 540 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1192 KB Output is correct
6 Correct 3 ms 1228 KB Output is correct
7 Correct 21 ms 3808 KB Output is correct
8 Correct 18 ms 3884 KB Output is correct
9 Correct 16 ms 3712 KB Output is correct
10 Correct 217 ms 22780 KB Output is correct
11 Correct 219 ms 22868 KB Output is correct
12 Correct 117 ms 15396 KB Output is correct
13 Correct 2208 ms 140216 KB Output is correct
14 Correct 2094 ms 140320 KB Output is correct
15 Correct 1904 ms 133116 KB Output is correct