# CFR 799 D. Field expansion ( Dummy Constraints, Greedy )

Problem - D - Codeforces

The first line contains five integers a, b, h, w and n (1 ≤ a, b, h, w, n ≤ 100 000) — the sizes of the rectangle needed to be placed, the initial sizes of the field and the number of available extensions.
The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 100 000), where ai equals the integer a side multiplies by when the i-th extension is applied.

dp[ i ][ j ][ k ]：已考慮前 i 個放大燈，已取 j 個放大燈，長放大 min( 1e5, k ) 倍時，寬最大可以放大多少。

O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );

int A, B, H, W, N;
int X[ MAXN ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> A >> B >> H >> W >> N;
swap( A, H );
swap( B, W );
for( int i = 0; i < N; ++i ) {
cin >> X[ i ];
}
sort( X, X + N, greater< int >() );
vector< int > bg2;
for( int i = 0; bg2.size() < 22 and i < N and X[ i ] > 2; ++i ) {
bg2.emplace_back( X[ i ] );
}
int ans = 0x3f3f3f3f;
for( int s = 0; s < 1 << bg2.size(); ++s ) {
int xx = 1, yy = 1;
int cx = __builtin_popcount( s );
int cy = 0;
for( int i = 0; i < bg2.size(); ++i ) {
if( s >> i & 1 ) {
xx = min( 1000000LL, 1LL * xx * bg2[ i ] );
} else {
if( 1LL * yy * B < W ) {
yy = min( 1000000LL, 1LL * yy * bg2[ i ] );
++cy;
}
}
}
int c2 = N - bg2.size();
while( c2 and 1LL * xx * A < H ) {
xx = min( 1000000LL, 2LL * xx );
++cx;
--c2;
}
while( c2 and 1LL * yy * B < W ) {
yy = min( 1000000LL, 2LL * yy );
++cy;
--c2;
}
if( 1LL * xx * A < H or 1LL * yy * B < W ) continue;
ans = min( ans, cx + cy );
}
swap( A, B );
for( int s = 0; s < 1 << bg2.size(); ++s ) {
int xx = 1, yy = 1;
int cx = __builtin_popcount( s );
int cy = 0;
for( int i = 0; i < bg2.size(); ++i ) {
if( s >> i & 1 ) {
xx = min( 1000000LL, 1LL * xx * bg2[ i ] );
} else {
if( 1LL * yy * B < W ) {
yy = min( 1000000LL, 1LL * yy * bg2[ i ] );
++cy;
}
}
}
int c2 = N - bg2.size();
while( c2 and 1LL * xx * A < H ) {
xx = min( 1000000LL, 2LL * xx );
++cx;
--c2;
}
while( c2 and 1LL * yy * B < W ) {
yy = min( 1000000LL, 2LL * yy );
++cy;
--c2;
}
if( 1LL * xx * A < H or 1LL * yy * B < W ) continue;
ans = min( ans, cx + cy );
}
if( ans == 0x3f3f3f3f ) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}
```