oj.uz

Submission #876806

# Submission time Handle Problem Language Result Execution time Memory
876806 2023-11-22T11:13:44 Z dsyz Quality Of Living (IOI10_quality) C++17
100 / 100
 2237 ms 246408 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
using ll = long long;
#define MAXN (3005)
ll A[MAXN][MAXN], dp[MAXN][MAXN];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	ll high = R * C + 5;
	ll low = 0;
	while(high - low > 1){
		ll mid = (high + low) / 2;
		memset(A,0,sizeof(A));
		for(ll i = 1;i <= R;i++){ //arrays A and dp are 1-indexed, Q is 0-indexed
			for(ll j = 1;j <= C;j++){
				if(Q[i - 1][j - 1] <= mid){
					A[i][j] = 1;
				}
			}
		}
		memset(dp,0,sizeof(dp));
		for(ll i = 1;i <= R;i++){
			for(ll j = 1;j <= C;j++){
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + A[i][j];
			}
		}
		ll maximum = 0;
		ll medianindex = ((H * W) + 1) / 2; //1-indexed
		for(ll i = 1;i <= R - H + 1;i++){
			for(ll j = 1;j <= C - W + 1;j++){
				ll b = i + H - 1;
				ll c = j + W - 1;
				ll sum = dp[b][c] - dp[i - 1][c] - dp[b][j - 1] + dp[i - 1][j - 1];
				maximum = max(maximum,sum);
			}
		}
		if(maximum >= medianindex){
			high = mid;	
		}else{
			low = mid;
		}
	}
	return high;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 142180 KB Output is correct
2 Correct 103 ms 142196 KB Output is correct
3 Correct 100 ms 142184 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 142180 KB Output is correct
2 Correct 103 ms 142196 KB Output is correct
3 Correct 100 ms 142184 KB Output is correct
4 Correct 133 ms 144300 KB Output is correct
5 Correct 135 ms 144288 KB Output is correct
6 Correct 137 ms 144216 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 142180 KB Output is correct
2 Correct 103 ms 142196 KB Output is correct
3 Correct 100 ms 142184 KB Output is correct
4 Correct 133 ms 144300 KB Output is correct
5 Correct 135 ms 144288 KB Output is correct
6 Correct 137 ms 144216 KB Output is correct
7 Correct 187 ms 146768 KB Output is correct
8 Correct 181 ms 146744 KB Output is correct
9 Correct 190 ms 146768 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 142180 KB Output is correct
2 Correct 103 ms 142196 KB Output is correct
3 Correct 100 ms 142184 KB Output is correct
4 Correct 133 ms 144300 KB Output is correct
5 Correct 135 ms 144288 KB Output is correct
6 Correct 137 ms 144216 KB Output is correct
7 Correct 187 ms 146768 KB Output is correct
8 Correct 181 ms 146744 KB Output is correct
9 Correct 190 ms 146768 KB Output is correct
10 Correct 405 ms 161364 KB Output is correct
11 Correct 391 ms 161240 KB Output is correct
12 Correct 292 ms 157816 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 142180 KB Output is correct
2 Correct 103 ms 142196 KB Output is correct
3 Correct 100 ms 142184 KB Output is correct
4 Correct 133 ms 144300 KB Output is correct
5 Correct 135 ms 144288 KB Output is correct
6 Correct 137 ms 144216 KB Output is correct
7 Correct 187 ms 146768 KB Output is correct
8 Correct 181 ms 146744 KB Output is correct
9 Correct 190 ms 146768 KB Output is correct
10 Correct 405 ms 161364 KB Output is correct
11 Correct 391 ms 161240 KB Output is correct
12 Correct 292 ms 157816 KB Output is correct
13 Correct 2237 ms 246408 KB Output is correct
14 Correct 2117 ms 246408 KB Output is correct
15 Correct 2138 ms 239328 KB Output is correct