SRM489 Div2 Medium(500) BuyingFlowers
rosesの要素数が小さいので全ての組み合わせを試すことが可能。バラとユリの個数の違いはR*Cが偶数ならば0、奇数ならば1。それぞれの面積に対して|R-C|の最小値を事前に求めておく。
#include <vector> #include <numeric> using namespace std; class BuyingFlowers{public: int buy( vector <int> roses, vector <int> lilies ) { int INF = 99999999; int n = (int)roses.size(); int M = accumulate( roses.begin(), roses.end(), 0 ) + accumulate( lilies.begin(), lilies.end(), 0 ); vector<int> sqr( M+1, INF ); for ( long long i=1; i<=M; i++ ) for ( long long j=i; i*j<=M; j++ ) sqr[i*j] = min( sqr[i*j], (int)(j-i) ); int ans = INF; for ( int i=0; i<(1<<n); i++ ) { int r = 0; int l = 0; for ( int j=0; j<n; j++ ) if ( i>>j & 1 ) r += roses[j], l += lilies[j]; if ( (r+l)%2 == 0 && abs(r-l) == 0 ) ans = min( ans, sqr[r+l] ); if ( (r+l)%2 == 1 && abs(r-l) == 1 ) ans = min( ans, sqr[r+l] ); } return ans<INF ? ans : -1; }};