CSAcademy Round #83 : D. Rectangle Fit

さすがに簡単目。
https://csacademy.com/contest/round-83/task/rectangle-fit/

問題

２次元座標において第１象限にN個の点の座標が与えられる。
軸に平行な長方形で面積がA以下の物のうち、１つの角が原点にあるようなものでできるだけ多くの点を覆いたい。
最大何個の点を覆うことができるか。

解法

幅Wを1からインクリメントしていくことを考える。
N個の点のうちX座標がW以下の物について、Y座標をmultiset等で管理し、A/Wより大きなものを外すという処理を行っていこう。
multisetの最大要素数が解となる。

なお、幅と同様に高さをインクリメントしていくことも試すとよい。

int N;
int X[101010],Y[101010];
ll A;
vector<int> V[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A;
	FOR(i,N) cin>>X[i]>>Y[i];
	
	int ma=0;
	FOR(i,2) {
		FOR(x,1010000) V[x].clear();
		FOR(x,N) {
			if(i) V[X[x]].push_back(Y[x]);
			else V[Y[x]].push_back(X[x]);
		}
		
		multiset<int> M;
		for(int x=1;x<=100000;x++) {
			FORR(e,V[x]) M.insert(-e);
			
			while(M.size() && 1LL*(-*M.begin())*x>A) M.erase(M.begin());
			ma=max(ma,(int)M.size());
		}
	}
	cout<<ma<<endl;
}

まとめ

まぁ定番かな…。