oj.uz

Submission #298471

# Submission time Handle Problem Language Result Execution time Memory
298471 2020-09-13T00:20:59 Z Hemimor Quality Of Living (IOI10_quality) C++14
100 / 100
 1931 ms 93816 KB 
#include "quality.h"
#include <iostream>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=0,r=R*C;
	auto f=[&](int x){
		int a[3001][3001];
		for(int i=0;i<=R;i++) for(int j=0;j<=C;j++) a[i][j]=0;
		for(int i=0;i<R;i++) for(int j=0;j<C;j++){
			a[i+1][j+1]=a[i][j+1]+a[i+1][j]-a[i][j]+(Q[i][j]<=x?1:0);
		}
/*		for(int i=0;i<=R;i++){
			for(int j=0;j<=C;j++) cout<<a[i][j]<<' ';
			cout<<endl;
		}
		cout<<endl;
		cout<<x<<' '<<H<<' '<<R<<' '<<W<<' '<<C<<endl;*/
		for(int i=H;i<=R;i++) for(int j=W;j<=C;j++){
//			cout<<i<<' '<<j<<' '<<a[i][j]-a[i-H][j]-a[i][j-W]+a[i-H][j-W]<<endl;
			if(a[i][j]-a[i-H][j]-a[i][j-W]+a[i-H][j-W]>H*W/2) return 1;
		}
		return 0;
	};
	while(r-l>1){
		int m=(l+r)/2;
		if(f(m)) r=m;
		else l=m;
	}
	return r;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Correct 1 ms 640 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 544 KB Output is correct
2 Correct 1 ms 640 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 544 KB Output is correct
2 Correct 1 ms 640 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 18 ms 3456 KB Output is correct
8 Correct 18 ms 3456 KB Output is correct
9 Correct 16 ms 3328 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Correct 1 ms 640 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 18 ms 3456 KB Output is correct
8 Correct 18 ms 3456 KB Output is correct
9 Correct 16 ms 3328 KB Output is correct
10 Correct 210 ms 16248 KB Output is correct
11 Correct 209 ms 22976 KB Output is correct
12 Correct 112 ms 15736 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Correct 1 ms 640 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 18 ms 3456 KB Output is correct
8 Correct 18 ms 3456 KB Output is correct
9 Correct 16 ms 3328 KB Output is correct
10 Correct 210 ms 16248 KB Output is correct
11 Correct 209 ms 22976 KB Output is correct
12 Correct 112 ms 15736 KB Output is correct
13 Correct 1931 ms 93760 KB Output is correct
14 Correct 1875 ms 93816 KB Output is correct
15 Correct 1764 ms 91348 KB Output is correct