POJ.3616 Milking Time

Problem
http://poj.org/problem?id=3616

Idea
dp[i]: best answer until i hours. The following recurrent equation is correct.
dp[i] = max(dp[i-1], dp[Inv.start] + v[Inv.value] | Inv ends at i);

Source

 int n, m, r;  
 int dp[2000006];  
 vector<vector<pair<int,int>>> a; // s, v  
 int main()  
 {  
      cin >> n >> m >> r;  
      a.resize(n + r + 1);  
      for (int i = 0; i < m; i++) {  
           int s, t, v;  
           cin >> s >> t >> v;  
           a[t + r].push_back(make_pair(s, v));  
      }  
      int ans = -1;  
      for (int i = 1; i <= n + r; i++) {  
           dp[i] = dp[i - 1];  
           for (int j = 0; j < a[i].size(); j++) {  
                int s = a[i][j].first;  
                int v = a[i][j].second;  
                dp[i] = max(dp[i], dp[s] + v);  
           }  
           ans = max(ans, dp[i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }