Submission #1233025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233025		matisito	Quality Of Living (IOI10_quality)	C++20	100 / 100	2289 ms	106256 KiB

quality

#include "quality.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<int>num;
	for(int i=0 ; i<R ; i++){
		for(int j=0 ; j<C ; j++){
			num.push_back(Q[i][j]);
		}
	}
	sort(num.begin(), num.end());
	int l=0, r=(int)num.size()-1;
	int ans=1e9;
	while(l<=r){
		int mid=(l+r)/2;
		int mid1=mid;
		mid=num[mid];
		vector<vector<int>>pref(R+1, vector<int>(C+1));
		for(int i=0 ; i<R ; i++){
			for(int j=0 ; j<C ; j++){
				if(Q[i][j]==mid) pref[i+1][j+1]=0;
				else if(Q[i][j]<mid) pref[i+1][j+1]=1;
				else pref[i+1][j+1]=-1;
			}
		}
		for(int i=1 ; i<=R ; i++){
			for(int j=1 ; j<=C ; j++){
				pref[i][j]+=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
			}
		}
		bool ok=0;
		for(int i=H ; i<=R ; i++){
			for(int j=W ; j<=C ; j++){
				if(pref[i][j]-pref[i-H][j]-pref[i][j-W]+pref[i-H][j-W]>=0){
					ok=1;
					break;
				}
			}
		}
		if(ok){
			r=mid1-1;
			ans=mid;
		}else l=mid1+1;
	}
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20