POJ 3616 Milking Time

ソースコード

int main()
{
    typedef pair<pint, int> P;
    int n, m, r;
    static vector<pint> g[ten(6) + 10]; // [start] => (end + r, efficiency)
    scanf("%d%d%d", &n, &m, &r);
    rep(i, m)
    {
	int s, e, ef;
	scanf("%d%d%d", &s, &e, &ef);
	if (e <= n)
	    g[s].pb(pint(min(n, e + r), ef));
    }

    static int dp[ten(6) + 10];	// (time)
    dp[0] = 0;
    rep(i, n)
    {
	chmax(dp[i + 1], dp[i]);
	rep(j, g[i].size())
	{
	    int restart = g[i][j].first;
	    int eff = g[i][j].second;
	    chmax(dp[restart], dp[i] + eff);
	}
    }
    printf("%d\n", dp[n]);
}