Submission #1233075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233075		porquenomedejainiciarsesion	Quality Of Living (IOI10_quality)	C++20	60 / 100	5093 ms	31664 KiB

quality

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
	int ans=100000000000;
	for(int k=0;k<R-H+1;k++){
	set<int> l,r,S;
	for(int i=k;i<H+k;i++){
		for(int j=0;j<W;j++){
			S.insert(Q[i][j]);
		}
	}
	int con=1;
	int act;
	for(auto x:S){
		if(con<=H*W/2){
			l.insert(x);
		}else if(con==H*W/2+1){
			act=x;
		}else{
			r.insert(x);
		}
		con++;
	}
	ans=min(ans,act);

	/////////////////////

	for(int i=W;i<C;i++){
		bool ok=true;
		for(int j=k;j<H+k;j++){
			l.erase(Q[j][i-W]);
			r.erase(Q[j][i-W]);
			if(Q[j][i]>act){
				r.insert(Q[j][i]);
			}else{
				l.insert(Q[j][i]);
			}
			if(Q[j][i-W]==act){
				ok=false;
			}
		}

		///////
		if(!ok){
			if(r.size()>l.size()){
				auto uwu=r.begin();
				act=*uwu;
				r.erase(*uwu);
			}else{
				auto uwu=l.end();
				uwu=prev(uwu);
				act=*uwu;
				l.erase(*uwu);
			}
		}

		//////

		if(r.size()>l.size()){
			int xd=r.size()-l.size();
			xd=xd/2;
			for(int i=0;i<xd;i++){
				auto uwu=r.begin();
				l.insert(act);
				act=*uwu;
				r.erase(*uwu);
			}
		}else{
			int xd=l.size()-r.size();
			xd=xd/2;
			for(int i=0;i<xd;i++){
				auto uwu=l.end();
				uwu=prev(uwu);
				r.insert(act);
				act=*uwu;
				l.erase(*uwu);
			}
		}
		ans=min(ans,act);
	}
	}
	return ans;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:5:17: warning: overflow in conversion from 'long int' to 'int' changes value from '100000000000' to '1215752192' [-Woverflow]
    5 |         int ans=100000000000;
      |                 ^~~~~~~~~~~~

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