SRM493 Div2 Hard(1000) CrouchingAmoebas

CrouchingAmoebas

スーパーアメーバーデストロイヤーを撃つ場所が決まっているなら、範囲外のアメーバーを近い順に範囲内に入れていけば良い。デストロイヤーは移動後のアメーバーが上端と左端に接する位置のみを考えれば充分。

#include <vector>
#include <algorithm>
using namespace std;

class CrouchingAmoebas{public:
int count( vector <int> x, vector <int> y, int A, int T )
{
    int n = (int)x.size();

    int ans = 0;

    for ( int a1=0; a1<n; a1++ )
    for ( long long sx=x[a1]-T; sx<=x[a1]+T; sx++ )
    for ( int a2=0; a2<n; a2++ )
    for ( long long sy=y[a2]-T; sy<=y[a2]+T; sy++ )
    {
        //  それぞれのアメーバと(sx,sy)-(sx+A,sy+A)の距離
        vector<long long> d(n);
        for ( int i=0; i<n; i++ )
            d[i] = ( x[i]<sx   ? sx-x[i]     : 0 )
                 + ( x[i]>sx+A ? x[i]-(sx+A) : 0 )
                 + ( y[i]<sy   ? sy-y[i]     : 0 )
                 + ( y[i]>sy+A ? y[i]-(sy+A) : 0 );
        sort(d.begin(),d.end());

        long long t = T;
        int i;
        for ( i=0; i<n && d[i]<=t; i++ )
            t -= d[i];
        ans = max( ans, i );
    }

    return ans;
}};