AOJ2290.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;
typedef long double ld;

const ld eps = 1e-9, pi = acos(-1.0);

#define MAX_V 10000
int V;

typedef ll Weight;
const Weight INF = 10000000000000000LL;
const Weight inf = 1e9;
// const Weight eps = 1e-8;

struct Edge{
  int src, dest;
  int cap, rev;
  Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

Weight h[MAX_V];                // potential
Weight dist[MAX_V];             // minimum distance
int prevv[MAX_V], preve[MAX_V]; // previous vertex and edge

void add_edge(Graph &g, int src, int dest, int cap, Weight weight) {
  g[src].push_back((Edge){src, dest, cap, (int)g[dest].size(), weight});
  g[dest].push_back((Edge){dest, src, 0, (int)g[src].size() - 1, -weight});
}

Weight min_cost_flow(Graph &g, int s, int t, int f) {
  Weight res = 0; V = g.size();
  memset(h, 0, sizeof(h));
  typedef pair<Weight, int> P;
  while (f > 0) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist, dist + V, INF);
    dist[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
      P p = que.top(); que.pop();
      int v = p.second;
      if (dist[v] < p.first) continue;
      REP(i, g[v].size()) {
        Edge &e = g[v][i];
        if (e.cap > 0 && dist[e.dest] > dist[v] + e.weight + h[v] - h[e.dest] /* + eps */) {
          dist[e.dest] = dist[v] + e.weight + h[v] - h[e.dest];
          prevv[e.dest] = v;
          preve[e.dest] = i;
          que.push(P(dist[e.dest], e.dest));
        }
      }
    }
    if (dist[t] == INF) return -1;
    REP(v, V) h[v] += dist[v];

    int d = f;
    for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
    f -= d;
    res += d * h[t];
    for (int v = t; v != s; v = prevv[v]) {
      Edge &e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return res;
}

int X[3000], T[3000], P[3000];
bool can[3000][3000];

int main() {
  int N, V, L, R;
  cin >> N >> V >> L >> R;
  Graph g(2*N+4);
  const int src = 2*N, dest = src + 1, left = src + 2, right = src + 3;
  vector<tuple<int,int,int>> vec;
  REP(i,N) {
    int x, t, p; cin >> x >> t >> p;
    vec.emplace_back(t, x, p);
  }
  sort(ALL(vec));
  REP(i,N) tie(T[i], X[i], P[i]) = vec[i];
  REP(i,N) REP(j,N) can[i][j] = (i != j && abs(X[i] - X[j]) <= V * (T[i] - T[j]));
  REP(i,N) {
    for (int k = N-1; k > i; --k) {
      if (!can[k][i]) continue;
      for (int j = i+1; j < k; ++j) {
        if (can[j][i] && can[k][j]) {
          can[k][i] = false;
          break;
        }
      }
    }
  }
  add_edge(g, src, left, 1, 0);
  add_edge(g, src, right, 1, 0);
  add_edge(g, src, dest, 2, inf * N);
  REP(i,N) {
    add_edge(g, i*2, i*2+1, 1, inf - P[i]);
    add_edge(g, i*2, i*2+1, 1, inf);
    if (abs(X[i] - L) <= V * T[i]) add_edge(g, left, i*2, 2, i*inf);
    if (abs(X[i] - R) <= V * T[i]) add_edge(g, right, i*2, 2, i*inf);
    add_edge(g, i*2+1, dest, 2, (N-i-1)*inf);
  }
  REP(i,N) REP(j,N)
    if (can[i][j]) add_edge(g, j*2+1, i*2, 2, (i-j-1)*inf);
  cout << inf * N * 2 - min_cost_flow(g, src, dest, 2) << endl;
  return 0;
}