SRM493 Div2 Hard(1000) 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; }};