Codeforces #413 D. Field expansion

詰めが甘くて結構レート減。
http://codeforces.com/contest/799/problem/D

問題

H*Wの長方形がある。
ここにN個のパラメータA[i]が与えられる。
パラメータのうちいくつかを選択し、各パラメータについて高さと幅いずれかにそのパラメータの数値を掛けることができる。
こうしてA*B以上の長方形にするには、最小で何個のパラメータを用いる必要があるか。

なお、長方形を90度回転させてもよい。

解法

パラメータは大きい順に使う方が得意なのは明らかである。
以下を考えよう。
S(i) := A[0]...A[i]のうちいくつかの積で表される集合
P(i) := A[0]...A[i]すべての積

x∈S(i)に対し、(H*x)と(W*(P(i)/x))の片方がA以上、もう片方がB以上なら(i+1)が解になる。
この際、A,Bは10^5以下なので、x≦10^5の範囲だけ考えればよい。
…としてS(i)を更新しつつ、条件を満たす最小のiを求めればよい。

ll A,B,H,W;
int N;
ll C[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>H>>W>>N;
	FOR(i,N) cin>>C[i];
	sort(C,C+N);
	reverse(C,C+N);
	N=min(35,N);
	
	if(max(H,W)>=max(A,B) && min(H,W)>=min(A,B)) return _P("0\n");
	
	set<ll> S;
	S.insert(1);
	ll tot=1;
	FOR(i,N) {
		set<ll> S2=S;
		if(tot*C[i]/C[i]!=tot) break;
		tot *= C[i];
		
		FORR(r,S2) S.insert(min(r*C[i],100000LL));
		int ok=0;
		FORR(r,S) {
			if(r*H>=A && (tot/r)*W>=B) ok=1;
			if(r*H>=B && (tot/r)*W>=A) ok=1;
		}
		if(ok) break;
	}
	if(i==N) cout<<-1<<endl;
	else cout<<i+1<<endl;
	
	
}

まとめ

本番中通知が上がらず、回転okなの気づかなかった。
なんでpretest通るんだ…。