VK Cup 2015 Round 1 : B. Group Photo 2 (online mirror version)

ひどい出来でした。Eで見当違いの方針で時間を食った上、Hackも出来ずレート落ち。
http://codeforces.com/contest/529/problem/B

問題

N人の人がいる。
それぞれ、立っていると写真上で縦H[i]ピクセル・横W[i]ピクセルの矩形分の面積を占める。
ただ、横に寝ると90度回転して縦W[i]横H[i]の矩形を占める。

N人の人が横に並んでいる状態を写真にとる。
その際の写真のサイズは、横幅のN人分の総和と、高さの最大値の積となる。
ここで、寝られるのは最大でN/2人であるとき、面積を最小化せよ。

解法

W・Hは高々1000なので、写真の高さを総当たりし、その中で横幅を最小化すればよい。

写真の高さが決まっているとして、縦も横もそれより大きい人がいる場合、その高さの写真は取れない。
縦と横片方が写真の高さを上回る場合、その人は横に寝るか寝ないか確定する。
縦も横も写真の高さ以下である場合、その人は縦でも横でも良い。
その場合、W[i]-H[i]が大きい人ほど、寝た方が横幅の総和を小さくできる。

そこで寝る人がN/2人に達するまでW[i]-H[i]が大きい順に寝かせればよい。

int N;
int W[1010],H[1010];
set<int> S;
ll mi=1LL<<50;

ll minw(int h) {
	ll tw=0;
	int i,tr=0;
	vector<pair<int,int> > V;
	
	FOR(i,N) {
		if(W[i]>h && H[i]>h) return 1LL<<50;
		if(H[i]>h) {
			tw+=H[i];
			if(++tr>N/2) return 1LL<<50;
		}
		else if(W[i]>h || W[i]<=H[i]) {
			tw+=W[i];
		}
		else {
			V.push_back(make_pair(H[i]-W[i],i));
		}
	}
	sort(V.begin(),V.end());
	FOR(i,V.size()) {
		if(tr+1<=N/2) tr++, tw += H[V[i].second];
		else tw += W[V[i].second];
	}
	return tw;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>W[i]>>H[i];
	for(i=1;i<=1000;i++) mi=min(mi,i*minw(i));
	
	cout<<mi<<endl;
	
}

まとめ

本番これはすんなり解けた。