oj.uz

Submission #292240

# Submission time Handle Problem Language Result Execution time Memory
292240 2020-09-06T15:00:57 Z amiratou Quality Of Living (IOI10_quality) C++14
100 / 100
 2253 ms 71048 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#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 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 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 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 21 ms 3456 KB Output is correct
8 Correct 20 ms 3456 KB Output is correct
9 Correct 19 ms 3320 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 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 21 ms 3456 KB Output is correct
8 Correct 20 ms 3456 KB Output is correct
9 Correct 19 ms 3320 KB Output is correct
10 Correct 241 ms 16120 KB Output is correct
11 Correct 235 ms 16248 KB Output is correct
12 Correct 129 ms 12280 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 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 21 ms 3456 KB Output is correct
8 Correct 20 ms 3456 KB Output is correct
9 Correct 19 ms 3320 KB Output is correct
10 Correct 241 ms 16120 KB Output is correct
11 Correct 235 ms 16248 KB Output is correct
12 Correct 129 ms 12280 KB Output is correct
13 Correct 2253 ms 70988 KB Output is correct
14 Correct 2194 ms 71048 KB Output is correct
15 Correct 2013 ms 70996 KB Output is correct