Codeforces #298 Div.2 B: Covered Path

さくっと解けたので満足。

問題

あなたはt秒間車を走らせることができる。車は1秒目には速度v1、t秒目には速度v2でなければならない（ともに正の整数）。車の速度を毎秒ごとに絶対値で最大dだけ変化させることができる。この条件のもとt秒間で進める距離の最大値を答えよ。

解法

貪欲的に解ける。各秒ごとの速度を持つことにして、まずt秒目まで車をひたすら加速させる。そのあとt秒目から逆向きに見ていき、最終速度におさまるように速度を抑えていけばいい。答えは速度の総和となる。

v1, v2 = map(int, raw_input().split())
t, d = map(int, raw_input().split())
speed = [0]*t
speed[0] = v1
for i in xrange(1,t-1):
    speed[i] = speed[i-1] + d
speed[-1] = v2

for i in xrange(t-2, 0, -1):
    speed[i] = min(speed[i+1]+d, speed[i])

print sum(speed)