Problem:


Score : 1200 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

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



Sample input:
3 9 1
1 3 8


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys


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

    ans = xxx[0] + (e - xxx[-1])

    i = 0
    while i < n:
        for j in range(i, n - 1):
            dx0 = xxx[j] - xxx[i]
            dx1 = xxx[j + 1] - xxx[i]
            stop = max(2 * dx0, t) + dx0 + xxx[j + 1] - xxx[j] + t
            through = max(2 * dx1, t) + dx1
            if stop < through:
                ans += stop - t
                i = j + 1
                break
        else:
            dx1 = xxx[n - 1] - xxx[i]
            ans += max(2 * dx1, t) + dx1
            i = n

    return ans


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

Submission status: Wrong Answer

Solution code:
N,E,T=map(int,input().split())
if N>2000:
    exit()
x=list(map(int,input().split()))
x=[0]+x

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

for i in range(N-1,-1,-1):
    dp[i]=min(max(T,2*x[j]-2*x[i+1])+dp[j]+x[j] for j in range(i+1,N+1))-x[i]

print(dp[0])

Submission status: Wrong Answer

Solution code:
N,E,T=map(int,input().split())
if N>2000:
    exit()
x=list(map(int,input().split()))
x=[0]+x

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

for i in range(N-1,-1,-1):
    test1=min(max(T,2*x[j]-2*x[i+1])+dp[j]+x[j] for j in range(i+1,N+1))-x[i]
    test2=x[N]-x[i]+T+x[N]-x[i+1]+abs(E-x[i+1])
    dp[i]=min(test1,test2)

print(dp[0])

Submission status: Wrong Answer

Solution code:
N,E,T=map(int,input().split())
if N>2000:
    exit()
x=list(map(int,input().split()))
x=[0]+x

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

for i in range(N-1,-1,-1):
    test1=min(max(T,2*x[j]-2*x[i+1])+dp[j]+x[j] for j in range(i+1,N+1))-x[i]
    test2=x[N]-x[i]+T+x[N]-x[i+1]+abs(E-x[N])
    dp[i]=min(test1,test2)

print(dp[0])

Submission status: Wrong Answer

Solution code:
N,E,T=map(int,input().split())
x=list(map(int,input().split()))
x=[0]+x

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

for i in range(N-1,-1,-1):
    test1=min(max(T,2*x[j]-2*x[i+1])+dp[j]+x[j] for j in range(i+1,N+1))-x[i]
    test2=x[N]-x[i]+T+x[N]-x[i+1]+abs(E-x[N])
    dp[i]=min(test1,test2)

print(dp[0])

Submission status: Wrong Answer

Solution code:
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**9 + 7
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])

Submission status: Wrong Answer

Solution code:
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():
    # これをseg木に乗せまーす
    dp = [0] * (N+1)
    for n in range(1,N+1):
        x = X[n]
        i = I[n]
        # i-1番目まで戻る → 待ち時間なし
        # i番目まで戻る → 待ち時間発生
        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)

if N >= 10**4:
    print(-1)
    exit()
base_solution()

Submission status: Wrong Answer

Solution code:
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()))

X2 = [2*x for x in X]
I = [bisect_left(X2,2*x-T) for x in X]

INF = 10**18

def base_solution():
    # これをseg木に乗せまーす
    dp = [0] * (N+1)
    for n in range(1,N+1):
        x = X[n]
        i = I[n]
        # i-1番目まで戻る → 待ち時間なし
        # i番目まで戻る → 待ち時間発生
        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)

if N >= 10**4:
    print(-1)
    exit()
base_solution()

Submission status: Wrong Answer

Solution code:
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()))

INF = 10**18

def base_solution():
    # これをseg木に乗せまーす
    dp = [0] * (N+1)
    for n in range(1,N+1):
        x = X[n]
        i = bisect_left(X,x-T/2)
        # i-1番目まで戻る → 待ち時間なし
        # i番目まで戻る → 待ち時間発生
        if i >= 1:
            t1 = min((dp[k]-X[k] for k in range(i-1,n)),default=INF)+x+T
        else:
            t1 = INF
        t2 = min((dp[k]-X[k]-2*X[k+1] for k in range(i-1)),default=INF)+3*x
        dp[n] = min(t1,t2)
    answer = dp[N] + (E-X[-1])
    print(answer)

base_solution()

Submission status: Wrong Answer

Solution code:
s=input().split();n,e,t=int(s[0]),int(s[1]),int(s[2])
s=input().split()
if (int(s[n-1])-int(s[0]))+t>t*n:
    print(e+t*n)
elif t>int(s[n-1])*2:
    print(int(s[0])+(int(s[n-1])-int(s[0]))+t+(e-int(s[0])))
else:
    print(int(s[0])+(int(s[n-1])-int(s[0]))*2+(e-int(s[0])))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, E, T = map(int, raw_input().split())
x = np.array(map(int, raw_input().split()))

dp = np.zeros(N, dtype='int')
for i in range(N):
    if i == 0:
        dp[i] = T
    else:
        dp[i] = (dp[0:i] + np.maximum(T, 2*(x[i] - x[1:(i+1)]))).min()

print dp[N-1] + E

Submission status: Wrong Answer

Solution code:
n, e, t = map(int, raw_input().split())
X = map(int, raw_input().split())

ans = 0
d = [0]*n
def f(j, i):
    return d[j] + max(2*(X[i] - X[j+1]), t) + X[i] - X[j]
d[0] = t
for i in xrange(1, n):
    d[i] = max(2*(X[i] - X[0]), t) + X[i] - X[0]
    le = 0; ri = i
    while 1:
        k1 = (le*2 + ri) / 3.
        k2 = (le + ri*2) / 3.
        r1 = f(int(k1), i)
        r2 = f(int(k2), i)
        if r1 <= r2:
            if ri == k2:break
            ri = k2
        else:
            if le == k1:break
            le = k1
    d[i] = min(d[i], r1, r2)
print d[n-1]+ e - X[-1] + X[0]

Submission status: Wrong Answer

Solution code:
n, e, t = map(int, raw_input().split())
X = map(int, raw_input().split())

if n > 2001:
    exit(1)
ans = 0
d = [0]*n
def f(j, i):
    return d[j] + max(2*(X[i] - X[j+1]), t) + X[i] - X[j]
d[0] = t
for i in xrange(1, n):
    d[i] = max(2*(X[i] - X[0]), t) + X[i] - X[0]
    le = 0; ri = i
    while 1:
        k1 = (le*2 + ri) / 3
        k2 = (le + ri*2) / 3
        r1 = f(k1, i)
        r2 = f(k2, i)
        if r1 <= r2:
            if ri == k2:break
            ri = k2
        else:
            if le == k1:break
            le = k1
    d[i] = min(d[i], r1, r2)
print d[n-1]+ e - X[-1] + X[0]

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, e, t = map(int, raw_input().split())
X = map(int, raw_input().split())

if n > 2001:
    exit(1)
ans = 0
bef = 0
bef_i = 0

d = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        d[i][j] = (j-i+1)*t + X[j] - X[i]
for i in xrange(n):
    for j in xrange(i):
        d[0][i] = min(d[0][j]+d[j+1][i]+(X[j+1]-X[j]), d[0][i])
print d[0][n-1]+e - X[-1] + X[0]

Submission status: Wrong Answer

Solution code:

N, E, T = map(int, raw_input().split())
X = map(int, raw_input().split())
hoge = []
 
for i in xrange(N):
    for j in xrange(i+1, N):
        d = X[j] - X[i]
        score = d*2+max(0, T-2*d) - (j-i+1)*T
        if score < 0:
            hoge.append((score, i, j))
hoge.sort()
piyo = []
for h in hoge:
    for p in piyo:
        if p[1] <= h[1] <= p[2] or p[1] <= h[2] <= p[2]:
            break
    else:
        piyo.append(h)
 
print E+T*N + sum(p[0] for p in piyo)

Submission status: Wrong Answer

Solution code:
N, E, T = map(int, raw_input().split())
X = map(int, raw_input().split())
hoge = []

for i in xrange(N):
    for j in xrange(i+1, N):
        d = X[j] - X[i]
        score = d*2+max(0, T-2*d) - (j-i+1)*T
        if score < 0:
            hoge.append((score, i, j))
hoge.sort()
piyo = []
for h in hoge:
    for p in piyo:
        if p[0] <= h[1] <= p[1] or p[0] <= h[2] <= p[1]:
            break
    else:
        piyo.append(h)

print E+T*N + sum(p[0] for p in piyo)

Submission status: Wrong Answer

Solution code:
n,e,t=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
dp1=[0]*(n+1)
dp1[n]=e-x[n]
dp2=[0]*(n+1)
dp2[n]=t+e-x[n]
for i in reversed(range(n)):
    dp1[i]=x[i+1]-x[i]+dp2[i+1]
    dp2[i]=min((x[i+1]-x[i])*3+dp1[i+1],t+x[i+1]-x[i]+dp2[i+1])
print dp1[0]

Submission status: Wrong Answer

Solution code:
N, E, T= map(int, raw_input().split())
nums = [int(t) for t in raw_input().split()]

time = nums[0]
i = 0

while i < len(nums):
    j = i
    while j < len(nums):
        if nums[j] - nums[i] < T:
            j += 1
        else:
            break
    length = nums[j-1] - nums[i]
    time += max(2 * length, T)
    if j < len(nums):
        time += nums[j] - nums[i]
        i = j
    else:
        time += E - nums[i] 
        i = j
        
print time

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, e, t = map(int, stdin.readline().split())
    x = map(int, stdin.readline().split(), repeat(10, n))
    x.append(e)
    i = 0
    ans = x[0]
    while i < n:
        j = i + 1
        while j < n and x[j] - x[i] <= t:
            j += 1
        ans += x[j] - x[i] + max(t, (x[j-1] - x[i]) * 2)
        i = j
    print ans
main()

Submission status: Time Limit Exceeded

Solution code:
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():
    # これをseg木に乗せまーす
    dp = [0] * (N+1)
    for n in range(1,N+1):
        x = X[n]
        i = I[n]
        # i-1番目まで戻る → 待ち時間なし
        # i番目まで戻る → 待ち時間発生
        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):
        # raw_data は 0-indexed
        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,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        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) # dp[k]-X[k] を格納する
dp2 = MinSegTree(N+1) # dp[k]-X[k]-2X[k+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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, E, T = map(int, raw_input().split())
x = np.array(map(int, raw_input().split()))

dp = np.zeros(N+1, dtype='int')
for i in range(N+1):
    if i == 0:
        dp[i] = 0
    else:
        dp[i] = (dp[0:i] + np.maximum(T, 2*(x[i-1] - x[0:i]))).min()

print dp[N] + E

Submission status: Time Limit Exceeded

Solution code:
n, e, t = map(int, input().split())
x = list(map(int, input().split()))
dp = [0] + [float('inf')] * n
for i in range(n):
    ndp = dp.copy()
    for j in range(i, n):
        ndp[j + 1] = min(dp[j + 1], dp[i] + max(t, 2 * (x[j] - x[i])))
    dp = ndp
print(e + dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, e, t = map(int, raw_input().split())
X = map(int, raw_input().split())

if n > 2001:
    exit(1)
ans = 0
bef = 0
bef_i = 0

d = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
    el = d[i]
    xi = X[i]
    for j in xrange(i, n):
        el[j] = max(2*(X[j] - xi), t) + X[j] - xi
for i in xrange(n):
    for j in xrange(i):
        d[0][i] = min(d[0][j]+d[j+1][i]+(X[j+1]-X[j]), d[0][i])
print d[0][n-1]+ e - X[-1] + X[0]

Submission status: Time Limit Exceeded

Solution code:
N, E, T = map(int, raw_input().split())
X = map(int, raw_input().split())
hoge = []

for i in xrange(N):
    for j in xrange(i+1, N):
        d = X[j] - X[i]
        score = d*2+max(0, T-2*d) - (j-i+1)*T
        if score < 0:
            hoge.append((score, i, j))
hoge.sort()
piyo = []
for h in hoge:
    for p in piyo:
        if p[0] <= h[1] <= p[1] or p[0] <= h[2] <= p[1]:
            break
    else:
        piyo.append(h[0])

print E+T*N + sum(piyo)

Submission status: Time Limit Exceeded

Solution code:
n,e,t=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
dp1=[0]*(n+1)
dp1[n]=e-x[n]
dp2=[0]*(n+1)
dp2[n]=t+e-x[n]
for i in reversed(range(n)):
    dp1[i]=x[i+1]-x[i]+dp2[i+1]
    u=[max(t,(x[j]-x[i])*2)+x[j]-x[i]+dp1[j] for j in range(i,n+1)]
    dp2[i]=min(u)
print dp1[0]

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
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=min(dp[j]+x[j] for j in range(i+1,id))+T
        test1=seg1.query(i+1,id)+T
    if N+1>id:
        #test2=min(3*x[j]+dp[j] for j in range(id,N+1))-2*x[i+1]
        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])
    #dp[i]=min(max(T,2*x[j]-2*x[i+1])+dp[j]+x[j] for j in range(i+1,N+1))-x[i]

print(dp[0])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:

"""
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 (dp)
print (E+N*T - dp[-1][0])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Runtime Error

Solution code:
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()))

X2 = [2*x for x in X]

INF = 10**18

def base_solution():
    # これをseg木に乗せまーす
    dp = [0] * (N+1)
    for n in range(1,N+1):
        x = X[n]
        i = bisect_left(X2,2*x-T)
        # i-1番目まで戻る → 待ち時間なし
        # i番目まで戻る → 待ち時間発生
        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)

if N >= 10**4:
    raise Exception
base_solution()

Submission status: Runtime Error

Solution code:
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()))

X2 = [2*x for x in X]

INF = 10**18

def base_solution():
    # これをseg木に乗せまーす
    dp = [0] * (N+1)
    for n in range(1,N+1):
        x = X[n]
        i = bisect_left(X2,2*x-T)
        # i-1番目まで戻る → 待ち時間なし
        # i番目まで戻る → 待ち時間発生
        if i >= 1:
            t1 = min((dp[k]-X[k] for k in range(i-1,n)),default=INF)+x+T
        else:
            t1 = INF
        t2 = min((dp[k]-X[k]-2*X[k+1] for k in range(i-1)),default=INF)+3*x
        dp[n] = min(t1,t2)
    answer = dp[N] + (E-X[-1])
    print(answer)

if N >= 10**4:
    raise Exception
base_solution()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
int n,k,e;
int main()
{
	cin>>n>>k>>e;
	cout<<k+n*e<<endl;
}