SRM489 Div2 Medium(500) BuyingFlowers

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;
}};