2015-2016 ACM-ICPC NEERC : B. Layer Cake

ここらへんはまだ簡単。Div1 AとBの間位か。
http://codeforces.com/contest/589/problem/B

問題

暑さ１のスポンジケーキがN個ある。
それぞれ縦横A[i]*B[i]の大きさの長方形をなしている。

これらのケーキを(元のどちらかの辺と平行な辺で)一部切り落としたうえで重ね、全体が直方体となるようにしたい。
(ケーキの向きは90度なら回転しても良い。また切り落とした部分は利用できない。)

得られる最大の体積を求めよ。

解法

まず１辺の大きさを総当たりする。
その候補は、A[i]またはB[i]である。

１辺の大きさを例えばpとする。
各ケーキにおいて、片方の辺をp以上にできるか判定し、できるならもう片方の辺ができるだけ長くなるようにケーキを回転する。
この「もう片方の辺の長さ」をソートすることで、「もう片方の辺の長さ」がある程度以上のものが何個とれるか簡単に求めることができる。

int N;
int A[4040],B[4040];
set<ll> S;
ll ma;
int w,h;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		S.insert(A[i]),S.insert(B[i]);
		if(A[i]>B[i]) swap(A[i],B[i]);
	}
	
	FORR(r,S) {
		vector<int> v;
		FOR(i,N) {
			if(A[i]>=r) v.push_back(B[i]);
			else if(B[i]>=r) v.push_back(A[i]);
		}
		sort(ALL(v));
		FOR(i,v.size()) {
			if(ma < r*v[i]*(v.size()-i)) {
				ma = r*v[i]*(v.size()-i);
				w = r;
				h = v[i];
			}
		}
	}
	
	cout<<ma<<endl;
	cout<<w<<" "<<h<<endl;
	
}

まとめ

内容の割に意外と正答者少ない？