oj.uz

Submission #403979

# Submission time Handle Problem Language Result Execution time Memory
403979 2021-05-13T16:11:00 Z Antekb Quality Of Living (IOI10_quality) C++14
100 / 100
 3091 ms 166500 KB 
#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int tab[R][C];
	vector<int> V;
	for(int i=0; i<R; i++){
		for(int j=0; j<C; j++){
			V.push_back(Q[i][j]);
		}
	}
	sort(V.begin(), V.end());
	int l=0, r=V.size()-1;
	while(l<r){
		bool b=0;
		int m=(l+r+1)>>1;
		int k=V[m];
		//cerr<<V[m]<<"\n";
		for(int i=0; i<R; i++){
			for(int j=0; j<C; j++){
				tab[i][j]=(Q[i][j]<k);
				//cout<<tab[i][j]<<" ";
			}
			//cout<<"\n";
		}
		for(int i=0; i<R; i++){
			for(int j=0; j<C; j++){
				if(i)tab[i][j]+=tab[i-1][j];
				if(j)tab[i][j]+=tab[i][j-1];
				if(i && j)tab[i][j]-=tab[i-1][j-1];
				//cout<<tab[i][j]<<" ";
				if(i>=H-1 && j>=W-1){
					int t=tab[i][j];
					if(i>=H)t-=tab[i-H][j];
					if(j>=W)t-=tab[i][j-W];
					if(i>=H && j>=W)t+=tab[i-H][j-W];
					if(t>H*W/2)b=1;
				}
			}
			//cout<<"\n";
		}
		//cerr<<b<<"\n";
		if(b)r=m-1;
		else l=m;
	}
	return V[l];
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 4 ms 928 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 4 ms 928 KB Output is correct
7 Correct 27 ms 3380 KB Output is correct
8 Correct 26 ms 3272 KB Output is correct
9 Correct 25 ms 3144 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 4 ms 928 KB Output is correct
7 Correct 27 ms 3380 KB Output is correct
8 Correct 26 ms 3272 KB Output is correct
9 Correct 25 ms 3144 KB Output is correct
10 Correct 329 ms 23216 KB Output is correct
11 Correct 325 ms 23092 KB Output is correct
12 Correct 157 ms 13616 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 4 ms 928 KB Output is correct
7 Correct 27 ms 3380 KB Output is correct
8 Correct 26 ms 3272 KB Output is correct
9 Correct 25 ms 3144 KB Output is correct
10 Correct 329 ms 23216 KB Output is correct
11 Correct 325 ms 23092 KB Output is correct
12 Correct 157 ms 13616 KB Output is correct
13 Correct 3091 ms 162704 KB Output is correct
14 Correct 3027 ms 166500 KB Output is correct
15 Correct 2802 ms 116864 KB Output is correct