Problem:
 ﻿Score : 400 points    Problem Statement In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express .  In the plan developed by the president Takahashi, the trains will run as follows:   A train will run for (t_1 + t_2 + t_3 + ... + t_N) seconds.  In the first t_1 seconds, a train must run at a speed of at most v_1 m/s (meters per second). Similarly, in the subsequent t_2 seconds, a train must run at a speed of at most v_2 m/s, and so on.   According to the specifications of the trains, the acceleration of a train must be always within ±1m/s^2 . Additionally, a train must stop at the beginning and the end of the run.  Find the maximum possible distance that a train can cover in the run.      Constraints  1 \leq N \leq 100  1 \leq t_i \leq 200  1 \leq v_i \leq 100  All input values are integers.         Input Input is given from Standard Input in the following format:  N  t_1  t_2  t_3 … t_N  v_1  v_2  v_3 … v_N       Output Print the maximum possible that a train can cover in the run. Output is considered correct if its absolute difference from the judge's output is at most 10^{-3} .        Sample Input 1 1
100
30      Sample Output 1 2100.000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 30 seconds, it accelerates at a rate of 1m/s^2 , covering 450 meters.  In the subsequent 40 seconds, it maintains the velocity of 30m/s , covering 1200 meters.  In the last 30 seconds, it decelerates at the acceleration of -1m/s^2 , covering 450 meters.   The total distance covered is 450 + 1200 + 450 = 2100 meters.       Sample Input 2 2
60 50
34 38      Sample Output 2 2632.000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 34 seconds, it accelerates at a rate of 1m/s^2 , covering 578 meters.  In the subsequent 26 seconds, it maintains the velocity of 34m/s , covering 884 meters.  In the subsequent 4 seconds, it accelerates at a rate of 1m/s^2 , covering 144 meters.  In the subsequent 8 seconds, it maintains the velocity of 38m/s , covering 304 meters.  In the last 38 seconds, it decelerates at the acceleration of -1m/s^2 , covering 722 meters.   The total distance covered is 578 + 884 + 144 + 304 + 722 = 2632 meters.       Sample Input 3 3
12 14 2
6 2 7      Sample Output 3 76.000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 6 seconds, it accelerates at a rate of 1m/s^2 , covering 18 meters.  In the subsequent 2 seconds, it maintains the velocity of 6m/s , covering 12 meters.  In the subsequent 4 seconds, it decelerates at the acceleration of -1m/s^2 , covering 16 meters.  In the subsequent 14 seconds, it maintains the velocity of 2m/s , covering 28 meters.  In the last 2 seconds, it decelerates at the acceleration of -1m/s^2 , covering 2 meters.   The total distance covered is 18 + 12 + 16 + 28 + 2 = 76 meters.       Sample Input 4 1
9
10      Sample Output 4 20.250000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 4.5 seconds, it accelerates at a rate of 1m/s^2 , covering 10.125 meters.  In the last 4.5 seconds, it decelerates at the acceleration of -1m/s^2 , covering 10.125 meters.   The total distance covered is 10.125 + 10.125 = 20.25 meters.       Sample Input 5 10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70      Sample Output 5 20291.000000000000

Solution (Python):
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
d_int = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	rest_t = [T[i]-now_t for i in range(N)]
	if now_v < v[now_n]:
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif now_v == v[now_n]: 
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 0
	for i in range(N):
		rest = rest_t[i]
		if rest > 0:
			d_v = now_v - v[i+1]
			if rest == d_v:
				a = -1

	d_int += 2 * int(now_v * 2) + a
	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d)

Solution (Python):
N = input()
t = map(int, raw_input().split())
v = map(int, raw_input().split())
v1 = [0]*N
v2 = [0]*N
for i in range(1,N):
    v1[i] = min(v1[i-1]+t[i-1], v[i-1], v[i])
for i in range(N-1)[::-1]:
    v2[i] = min(v2[i+1]+t[i+1], v[i+1], v[i])
for i in range(N):
    v1[i] = min(v1[i], v2[i]+t[i])
    v2[i] = min(v1[i]+t[i], v2[i])
ans = 0
for i in range(N):
    vm = min((v1[i]+v2[i]+t[i])*.5, v[i]*1.)
    ans += (vm-v1[i])**2*.5 + (vm-v1[i])*v1[i] + (vm-v2[i])**2*.5 + (vm-v2[i])*v2[i] + vm*(t[i]-(vm-v1[i])-(vm-v2[i]))
print "%.10f"%ans

Solution (Python):
N = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))

sumT = sum(ts)
va = [min(i / 2, sumT - i / 2) for i in range(2 * sumT + 1)]

accT = 0
for t, v in zip(ts, vs):
    for i in range(accT, accT + 2 * t + 1):
        va[i] = min(va[i], v)
    accT += t * 2

for i in range(len(va) - 1):
    if va[i + 1] - va[i] > 0.5:
        va[i + 1] = va[i] + 0.5

for i in range(len(va) - 1)[::-1]:
    if va[i] - va[i + 1] > 0.5:
        va[i] = va[i + 1] + 0.5

print(sum(va) / 2)

Solution (Python):
N = int(input())
tt = map(int, input().split())
vv = map(int, input().split())

v_now = 0
v_max = [v_now]
for t, v in reversed(list(zip(tt, vv))):
    for i in range(t * 2):
        if v_now + 0.5 <= v:
            v_now += 0.5
        else:
            v_now = min(v_now, v)
        v_max.append(v_now)
v_max = v_max[::-1]

v = 0
total = 0
for i in range(len(v_max) - 1):
    v0 = v_max[i]
    v1 = v_max[i+1]
    if v + 0.5 <= v1:
        if v < v0:
            total += (v + v + 0.5) * 0.25
            v += 0.5
        else:
            total += v * 0.5
    elif v > v1:
        total += (v + v - 0.5) * 0.25
        v -= 0.5
        assert v == v1, '%s %s'%(v,v1)
    else:
        total += v * 0.5
print(total)

Solution (Python):
from fractions import Fraction as F

N = input()
T = map(int, raw_input().split())
V = map(int, raw_input().split())

VL = [V[i] for i in xrange(N)]
VL.append(0)
for i in xrange(N-1, -1, -1):
    VL[i] = min(VL[i], VL[i+1] + T[i])

v1 = F(0)
v2 = F(0)
ans = F(0)

for i in xrange(N):
    t1 = F(0)
    v2 = F(v1)

    while t1 < T[i] and v2 < V[i] and v2 - (T[i] - t1) < VL[i+1]:
        t1 += F(1, 2)
        v2 += F(1, 2)
    v2 = v1 + t1
    ans += (v1 + v2) / F(2) * t1

    t2 = F(0)
    while t1 + t2 < T[i] and v2 - (T[i] - t1 - t2) < VL[i+1]:
        t2 += F(1, 2)
    ans += v2 * t2

    v3 = v2 - (T[i] - t1 - t2)
    ans += (v2 + v3) / F(2) * (T[i] - t1 - t2)

    v1 = v3

print "%.09f" % ans

Solution (Python):
N = input()
T = map(int, raw_input().split())
V = map(int, raw_input().split())

VL = [V[i] for i in xrange(N)]
VL.append(0)
for i in xrange(N-1, -1, -1):
    VL[i] = min(VL[i], VL[i+1] + T[i])

v1 = 0
v2 = 0
ans = 0

for i in xrange(N):
    t1 = 0
    v2 = v1

    hi = T[i] * 1.0
    lo = 0
    for _ in xrange(100):
        mid = (hi + lo) / 2
        tt = t1 + mid
        vv = v2 + mid
        if tt <= T[i] and vv <= V[i] and vv - (T[i] - tt) <= VL[i+1]:
            lo = mid
        else:
            hi = mid

    t1 += hi
    v2 = v1 + t1
    ans += (v1 + v2) / 2.0 * t1

    hi = (T[i] - t1) * 1.0
    lo = 0
    for _ in xrange(100):
        mid = (hi + lo) / 2
        tt = mid
        if t1 + tt <= T[i] and v2 - (T[i] - t1 - tt) < VL[i+1]:
            lo = mid
        else:
            hi = mid

    t2 = hi
    ans += v2 * t2

    v3 = v2 - (T[i] - t1 - t2)
    ans += (v2 + v3) / 2.0 * (T[i] - t1 - t2)

    v1 = v3

print "%.09f" % ans

Solution (Python):
n = int(input())
ts = [int(c) for c in input().split()]
vs = [int(c) for c in input().split()]

t = sum(ts)
dp = [[-10 ** 10 for _ in range(101)] for _ in range(t + 1)]
dp[0][0] = 0.

mvs = []
for dt, mv in zip(ts, vs):
    for st in range(dt):
        mvs.append(mv)
mvs.append(0)

for ct in range(t):
    mv = mvs[ct]
    for cv in range(mv + 1):
        endmv = min(mv, mvs[ct+1])
        for dv in [-1, 0, 1]:
            nv = cv + dv
            if 0 <= nv <= endmv:
                dp[ct + 1][nv] = max(dp[ct][cv] + (cv + nv) / 2, dp[ct + 1][nv])
        if mv >= cv + 1 and cv <= endmv:
            dp[ct + 1][cv] = max(dp[ct+1][cv], dp[ct][cv] + cv + 0.25)


print(dp[t][0])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    t = LI()
    u = LI()
    a = [inf] * n
    b = [inf] * n
    a[0] = 0
    b[0] = min(t[0],u[0])
    b[-1] = 0
    a[-1] = min(a[-1],t[-1],u[-1])
    for i in range(1,n):
        a[i] = min(a[i],b[i-1],u[i])
        b[i] = min(b[i],a[i]+t[i],u[i])
    for i in range(n-2,-1,-1):
        b[i] = min(b[i],a[i+1],u[i])
        a[i] = min(a[i],b[i]+t[i],u[i])
    r = 0
    for i in range(n):
        c = a[i]
        d = b[i]
        e = u[i]
        f = t[i]
        k = abs(c-d)
        m = max(c,d)
        l = min(m + (f-k) / 2.0,e)
        ct = l-c
        r += c*ct + ct*(l-c) / 2.0
        dt = l-d
        r += d*dt + dt*(l-d) / 2.0
        r += l * (f-ct-dt)

    return r


print(main())

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
t = na()
v = na()

bound = [0] * (n+1)
for i in range(n-1):
    bound[i+1] = min(v[i], v[i+1], bound[i] + t[i])
for i in range(n-1,0,-1):
    bound[i] = min(bound[i], v[i], v[i-1], bound[i+1] + t[i])

ans = 0
for i in range(n):
    l = bound[i]
    r = bound[i+1]
    
    
    x = (r-l+t[i])/2
    if l + x <= v[i]:
        ans += (l + (l + x)) * x / 2 + (l + x + r) * (t[i] - x) / 2
    else:
        ans += (v[i] + l) * (v[i] - l) / 2 + (v[i] + r) * (v[i] - r) / 2
        ans += (t[i] - (v[i] - l) - (v[i] - r)) * v[i]
print("{:.14f}".format(ans))