oj.uz

Submission #519737

# Submission time Handle Problem Language Result Execution time Memory
519737 2022-01-27T08:03:33 Z drkarlicio2107 Quality Of Living (IOI10_quality) C++14
100 / 100
 2114 ms 116232 KB 
#include <bits/stdc++.h>
using namespace std;
int pref [3010][3010]; int l [3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){ 
	int lo=0, hi=R*C;
	while(lo<hi){
		//cout << lo << " " << hi << endl;
		int mid=(lo+hi+1)/2;
		int da=0;
		for (int i=1; i<R+1; i++){
			for (int j=1; j<C+1; j++){
				if(Q[i-1][j-1]<mid) l[i][j]=-1;
				else if(Q[i-1][j-1]>mid) l[i][j]=1;
				else l[i][j]=0;
				pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+l[i][j];
				if(i>=H && j>=W) if (pref[i][j]-pref[i-H][j]-pref[i][j-W]+pref[i-H][j-W]<0) da=1;
				//cout << pref[i][j] << "x" << l[i][j] << " ";
			}
			//cout << endl;
		}
		if(da) hi=mid-1;
		else lo=mid;
	}
	return lo;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 684 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 684 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 18 ms 5452 KB Output is correct
8 Correct 26 ms 5444 KB Output is correct
9 Correct 16 ms 5328 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 684 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 18 ms 5452 KB Output is correct
8 Correct 26 ms 5444 KB Output is correct
9 Correct 16 ms 5328 KB Output is correct
10 Correct 226 ms 30796 KB Output is correct
11 Correct 219 ms 30776 KB Output is correct
12 Correct 111 ms 21416 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 684 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 18 ms 5452 KB Output is correct
8 Correct 26 ms 5444 KB Output is correct
9 Correct 16 ms 5328 KB Output is correct
10 Correct 226 ms 30796 KB Output is correct
11 Correct 219 ms 30776 KB Output is correct
12 Correct 111 ms 21416 KB Output is correct
13 Correct 2114 ms 116232 KB Output is correct
14 Correct 1991 ms 116100 KB Output is correct
15 Correct 1876 ms 114860 KB Output is correct