Problem:
 Score : 1200 points    Problem Statement  Imagine a game played on a line. Initially, the player is located at position 0 with N candies in his possession, and the exit is at position E . There are also N bears in the game. The i -th bear is located at x_i . The maximum moving speed of the player is 1 while the bears do not move at all.  When the player gives a candy to a bear, it will provide a coin after T units of time. More specifically, if the i -th bear is given a candy at time t , it will put a coin at its position at time t+T . The purpose of this game is to give candies to all the bears, pick up all the coins, and go to the exit. Note that the player can only give a candy to a bear if the player is at the exact same position of the bear. Also, each bear will only produce a coin once. If the player visits the position of a coin after or at the exact same time that the coin is put down, the player can pick up the coin. Coins do not disappear until collected by the player.  Shik is an expert of this game. He can give candies to bears and pick up coins instantly. You are given the configuration of the game. Please calculate the minimum time Shik needs to collect all the coins and go to the exit.      Constraints  1 \leq N \leq 100,000  1 \leq T, E \leq 10^9  0 < x_i < E  x_i < x_{i+1} for 1 \leq i < N  All input values are integers.       Partial Scores  In test cases worth 600 points, N \leq 2,000 .         Input The input is given from Standard Input in the following format:  N  E  T  x_1  x_2  ...  x_N       Output Print an integer denoting the answer.        Sample Input 1 3 9 1
1 3 8      Sample Output 1 12  The optimal strategy is to wait for the coin after treating each bear. The total time spent on waiting is 3 and moving is 9 . So the answer is 3 + 9 = 12 .       Sample Input 2 3 9 3
1 3 8      Sample Output 2 16       Sample Input 3 2 1000000000 1000000000
1 999999999      Sample Output 3 2999999996

Solution (Python):
import sys
from bisect import bisect, bisect_left


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.INF = 10 ** 18
        self.tree = [self.INF] * (n + 1)

    def get_min(self, i):
        s = self.INF
        while i > 0:
            s = min(s, self.tree[i])
            i -= i & -i
        return s

    def update(self, i, x):
        while i <= self.size:
            if self.tree[i] <= x:
                break
            self.tree[i] = x
            i += i & -i


def solve(n, e, t, xxx):
    if n == 1:
        return e + t

    dp1 = [0] * (n + 1)
    dp2 = BinaryIndexedTree(n + 1)
    dp2.update(1, -xxx[0] * 2)

    for i in range(n):
        x = xxx[i]
        j = bisect_left(xxx, x - t // 2, hi=i)
        ex_time = dp1[j] + t
        if j > 0:
            ex_time = min(ex_time, x * 2 + dp2.get_min(j))
        dp1[i + 1] = ex_time
        if i < n - 1:
            dp2.update(i + 2, ex_time - xxx[i + 1] * 2)

    return e + dp1[-1]


n, e, t, *xxx = map(int, sys.stdin.buffer.read().split())
print(solve(n, e, t, xxx))

Solution (Python):

def segfunc(x, y):
    return min(x,y)



ide_ele = float("inf")


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, n, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import bisect,random

N,E,T=map(int,input().split())
x=list(map(int,input().split()))
x=[0]+x
X=[2*x[i] for i in range(N+1)]



dp=[0 for i in range(N+1)]
dp[N]=abs(E-x[N])

seg1=SegTree(N+1,segfunc,ide_ele)
seg3=SegTree(N+1,segfunc,ide_ele)
seg1.update(N,E-x[N]+x[N])
seg3.update(N,E-x[N]+3*x[N])

for i in range(N-1,-1,-1):
    id=bisect.bisect_right(X,T+2*x[i+1])
    test,test2=10**20,10**20
    if id>i+1:
        
        test1=seg1.query(i+1,id)+T
    if N+1>id:
        
        test2=seg3.query(id,N+1)-2*x[i+1]
    dp[i]=min(test1,test2)-x[i]
    seg1.update(i,dp[i]+x[i])
    seg3.update(i,dp[i]+3*x[i])
    

print(dp[0])

Solution (Python):
import sys
readline = sys.stdin.readline

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            pre = self.data[l+self.N0]
            for idx in (SL + SR[::-1]):
                if not check(self.segf(pre, self.data[idx])):
                    pre = self.segf(pre, self.data[idx])
                else:
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(pre, self.data[2*idx])):
                    idx = 2*idx
                else:
                    pre = self.segf(pre, self.data[2*idx])
                    idx = 2*idx + 1
            return idx - self.N0


INF = 10**18 + 3
N, E, T = map(int, readline().split())
X = list(map(int, readline().split()))
X = [0] + [x-X[0]  for x in X] + [INF]
E -= X[0]
dp = [0]*(N+2)
dpl = Segtree([0]*(N+2), INF, initialize = False, segf = min)
dpr = Segtree([0]*(N+2), INF, initialize = False, segf = min)
dpl.update(0, 0)
dpr.update(0, 0)

for i in range(1, N+1):
    di = X[i]
    dn = X[i+1]
    ok = i
    ng = -1
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        if (X[i] - X[med])*2 <= T:
            ok = med
        else:
            ng = med
    left = ok-1
    resr = dpr.query(left, i) + T + di
    resl = dpl.query(0, left) + 3*di
    dp[i] = min(resl, resr)
    dpl.update(i, dp[i] - di - 2*dn)
    dpr.update(i, dp[i] - di)

print(dp[N] + E - X[N])

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc007/tasks/agc007_d

まぁdpだよね
選択は
1.前の奴から引き継ぐ
2.新たに始める
の2択か？

ABCDの4つを同時に回収するとき
Aアメ→Dコインまでの時間は
max(3*(D-A),T+D-A)

待ち時間がちょうどないくらいが望ましいはず
すなわち、2*(D-A)と Tの差が小さくなるように選ぶべき？

左から歩いて行き、毎回止まって待つ場合
時間はE+NTである
ここからどれだけ減らせるかを基準に考えてみよう

T以内にx個追加で回ってこれた場合、減少するのはxT
x個回ってきたが、aだけ時間制限を超えた場合、減少はxT-a
少なくとも回れるならばすべて回ったほうが良い→右方向T/2以下にあるやつは確定で同時に取る
そうでない場合、新たに始める or x-増加分　のコストを払うを選択できる

これをうまくdpに落とし込めないか？？

dp[ai][連続/始点] = その頂点が始点 or 連続点の場合の減少量の最大値
始点は,T/2より1つだけ右にある要素にあげるdpをする(二分探索で位置を求める)
連続の場合、+1のところの連続or始点にあげるdpをする

あげるものは、E+NTからの減少量。よって最大値を求める

始点から上げる場合
iからT/2より+1右にある要素jの始点にあげる場合、(j-i-1)*T 可算
連続にあげる場合は、あまり分を考慮
(j-i)*T - 2*(A[j]-A[i])-T

連続から始点にあげる場合、+-0であげちゃう
連続から連続にあげる場合、T-(A[i+1]-A[i])*2 可算

大体おｋだと思うけど　始点と終点の処理は？
始点は考慮する必要無し
終点は…ちょっと面倒くさい　座標infをおいておけばいいかな
座標infの始点が答えになりそう
"""
import bisect
N,E,T = map(int,input().split())

A = list(map(int,input().split()))
A.append(float("inf"))

dp = [[float("-inf")] * 2 for i in range(N+1)]
dp[0][0] = 0

for i in range(N):

    j = bisect.bisect_right(A,A[i] + T//2)
    dp[j][0] = max(dp[j][0] , dp[i][0] + (j-i-1)*T )
    dp[j][1] = max(dp[j][1] , dp[i][0] + (j-i)*T - (2*(A[j]-A[i]) - T) )

    dp[i+1][0] = max(dp[i+1][0] , dp[i][1])
    dp[i+1][1] = max(dp[i+1][1] , dp[i][1] + T - (A[i+1]-A[i])*2 )


print (E+N*T - dp[-1][0])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left

N,E,T = map(int,readline().split())
X = [0] + list(map(int,read().split()))

half = T//2
I = [bisect_left(X,x-half) for x in X]

INF = 10**18

def base_solution():
    
    dp = [0] * (N+1)
    for n in range(1,N+1):
        x = X[n]
        i = I[n]
        
        
        if i >= 1:
            t1 = min((dp[k]-X[k] for k in range(i-1,n)),default=INF)+x+T
            t2 = min((dp[k]-X[k]-2*X[k+1] for k in range(i-1)),default=INF)+3*x
        else:
            t1 = min((dp[k]-X[k] for k in range(n)),default=INF)+x+T
            t2 = INF
        dp[n] = min(t1,t2)
    answer = dp[N] + (E-X[-1])
    print(answer)

class MinSegTree():
    def __init__(self,N):
        self.Nelem = N
        self.size = 1<<(N.bit_length()) 
        
    def build(self,raw_data):
        
        INF = 10**18
        self.data = [INF] * (2*self.size)
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
            i >>= 1
    
    def get_value(self,L,R):
        
        L += self.size
        R += self.size + 1
        
        x = 10**18
        while L < R:
            if L&1:
                y = self.data[L]
                if x > y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x > y: x = y
            L >>= 1; R >>= 1
        return x

dp1 = MinSegTree(N+1) 
dp2 = MinSegTree(N+1) 
dp1.build([0]*(N+1))
dp2.build([0]*(N+1))
dp2.update(0,-2*X[1])
X.append(E)
for n in range(1,N+1):
    x = X[n]; i = I[n]
    if i >= 1:
        t1 = dp1.get_value(i-1,n-1)+x+T
        t2 = dp2.get_value(0,i-2)+3*x
        t = t1 if t1<t2 else t2
    else:
        t = dp1.get_value(0,n-1)+x+T
    dp1.update(n,t-x)
    dp2.update(n,t-x-2*X[n+1])
answer = t+E-x
print(answer)

Solution (Python):
n,e,t=map(int,input().split())
a,f,l,c=[0]+list(map(int,input().split())),[0]*(n+1),1,int(1e18)
for i in range(1,n+1):
	while 2*(a[i]-a[l])>=t:
		c=min(c,f[l-1]-2*a[l])
		l+=1
	f[i]=min(f[l-1]+t,c+2*a[i])
print(f[n]+e)

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n, e, t = map(int, stdin.readline().split())
    x = [0] + map(int, stdin.readline().split(), repeat(10, n)) + [e]
    dp = [0] * (n + 1)
    f = [0] * (n + 1)
    f[0] = -x[1] * 2
    j = 0
    for i in xrange(1, n + 1):
        while j < i - 1 and (x[i] - x[j+1]) * 2 > t:
            j += 1
        dp[i] = dp[j] + t
        if j > 0 and dp[i] > f[j-1] + x[i] * 2:
            dp[i] = f[j-1] + x[i] * 2
        f[i] = dp[i] - x[i+1] * 2
        if i and f[i] > f[i-1]:
            f[i] = f[i-1]
    print dp[n] + e
main()