oj.uz

Submission #292239

# Submission time Handle Problem Language Result Execution time Memory
292239 2020-09-06T14:59:23 Z amiratou Quality Of Living (IOI10_quality) C++14
100 / 100
 2453 ms 103572 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int cum[3001][3001];
int sum(int a,int b,int c,int d){
	int ans=cum[c][d];
	if(a)ans-=cum[a-1][d];
	if(b)ans-=cum[c][b-1];
	if(a && b)ans+=cum[a-1][b-1];
	return ans;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=1,r=R*C,cons=(H*W)/2,ans=-1;
	while(l<=r){
		int med=(l+r)>>1;
		for (int i = 0; i < R; ++i)
			for (int j = 0; j < C; ++j)
			{
				cum[i][j]=(Q[i][j]<=med);
				if(i)cum[i][j]+=cum[i-1][j];
				if(j)cum[i][j]+=cum[i][j-1];
				if(i&&j)cum[i][j]-=cum[i-1][j-1];
			}
		bool f=0;
		for (int i = 0; i+H-1 < R; ++i)
		{
			for (int j = 0; j+W-1 < C; ++j)
				if(sum(i,j,i+H-1,j+W-1)>(cons)){
					f=1;break;
				}
			if(f)break;
		}
		if(f)r=med-1,ans=med;
		else l=med+1;
	}
	assert(ans!=-1);
	return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 22 ms 3976 KB Output is correct
8 Correct 22 ms 3968 KB Output is correct
9 Correct 20 ms 3840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 22 ms 3976 KB Output is correct
8 Correct 22 ms 3968 KB Output is correct
9 Correct 20 ms 3840 KB Output is correct
10 Correct 268 ms 22844 KB Output is correct
11 Correct 261 ms 22904 KB Output is correct
12 Correct 138 ms 15608 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 22 ms 3976 KB Output is correct
8 Correct 22 ms 3968 KB Output is correct
9 Correct 20 ms 3840 KB Output is correct
10 Correct 268 ms 22844 KB Output is correct
11 Correct 261 ms 22904 KB Output is correct
12 Correct 138 ms 15608 KB Output is correct
13 Correct 2453 ms 103572 KB Output is correct
14 Correct 2404 ms 93024 KB Output is correct
15 Correct 2193 ms 90716 KB Output is correct