SRM404 Div2 Hard

1000

同じ高さで到達可能なモノを1つにまとめる。
まとめると、よくあるDPになる。

const int N = 50 + 1;

typedef complex<double> Point;

double dot(Point a, Point b)
{
  return (a.real() * b.real() + a.imag() * b.imag());
}

double cross(Point a, Point b)
{
  return (a.real() * b.imag() - a.imag() * b.real());
}

double distance_lp(Point a1, Point a2, Point b)
{
  if(dot(a2-a1, b-a1) < EPS)return abs(b-a1);
  if(dot(a1-a2, b-a2) < EPS)return abs(b-a2);
  return abs(cross(a2-a1, b-a1)) / abs(a2-a1);
}

double distance_ll(Point a1, Point a2, Point b1, Point b2)
{
  double a = min(distance_lp(a1, a2, b1), distance_lp(a1, a2, b2));
  double b = min(distance_lp(b1, b2, a1), distance_lp(b1, b2, a2));
  return min(a, b);
}

class DisjointSet{
public:
  vector<int> rank, p;
  DisjointSet(int size)
  {
    rank.resize(size, 0);
    p.resize(size, 0);
  }
  void make(int a)
  {
    rank[a] = 0;
    p[a] = a;
  }
  void join(int a, int b)
  {
    link(find(a), find(b));
  }
  int find(int a)
  {
    return (a == p[a])? a : p[a] = find(p[a]);
  }
  bool isSameSet(int a, int b)
  {
    return find(a) == find(b);
  }
  void link (int a, int b)
  {
    if(rank[a] > rank[b]) p[b] = a;
    else {
      p[a] = b;
      if(rank[a] == rank[b]) rank[b]++;
    }
  }
};

int K;
vector<int> X, Y, L, S;

bool reach(int i, int j)
{
  Point a1(X[i], Y[i]);
  Point a2(X[i] + L[i], Y[i]);
  Point b1(X[j], Y[j]);
  Point b2(X[j] + L[j], Y[j]);
  return distance_ll(a1, a2, b1, b2) <= (double)K;
}

bool g[N][N];
int ss[N];

int memo[N];
int rec(int n)
{
  int &ret = memo[n];
  if (ret != -1) return ret;
   
  int mx = 0;
  for (int m = 0; m < (int)N; ++m) {
    if (g[n][m]) mx = max(mx, rec(m));
  }

  return ret = mx + ss[n];
}

class GetToTheTop {
public:
  int collectSweets(int K_, vector <int> S_, vector <int> X_, vector <int> Y_, vector <int> L_)
  {
    K = K_;
    X = X_;
    Y = Y_;
    L = L_;
    S = S_;

    const int size = L.size();
    DisjointSet uf(size);

    for (int i = 0; i < (int)size; ++i) {
      uf.make(i);
    }

    for (int i = 0; i < (int)size; ++i) {
      for (int j = i + 1; j < (int)size; ++j) {       
        if (Y[i] == Y[j] && reach(i, j)) {
          uf.join(i, j);
        }
      }
    }
   
    fill(&g[0][0], &g[N - 1][N], false);
    fill(ss, ss + N, 0);

    for (int i = 0; i < (int)size; ++i) {
      ss[uf.find(i)] += S[i];
    }

    for (int i = 0; i < (int)size; ++i) {
      for (int j = 0; j < (int)size; ++j) {
        if (uf.isSameSet(i, j)) continue;
        if (Y[i] < Y[j] && reach(i, j)) {
          int src = uf.find(i);
          int dst = uf.find(j);
          g[src][dst] = true;
        }
      }
    }

    fill(memo, memo + N, -1);

    int mx = 0;
    for (int i = 0; i < (int)size; ++i) {
      if (Y[i] <= K) {
        mx = max(mx, rec(uf.find(i)));
      }
    }

    return mx;
  }
};