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=[int(x) for x in input().split()]
V=[int(x) for x in input().split()]

def solve(N, T, V):
    from itertools import accumulate
    ds = [0] + list(accumulate(T))
    vs = [0] + [min(V[i], V[i + 1]) for i in range(len(V) - 1)] + [0]
    for i in range(len(vs)):
        d = ds[i]
        vs[i] = min([v + abs(d - ds[j]) for j, v in enumerate(vs)])
    def calc(t, v0, v1, maxv):
        t0 = maxv - v0
        t1 = maxv - v1
        if t0 + t1 < t:
            return t * maxv - t0 * t0 / 2 - t1 * t1 / 2
        else:
            t0 = (t + v1 - v0) / 2
            t1 = (t + v0 - v1) / 2
            v = (t + v0 + v1) / 2
            S = v * t - t0 * t0 / 2 - t1 * t1 / 2
            return S
    r = 0
    for i in range(N):
        c = calc(T[i], vs[i], vs[i + 1], V[i])
        r += c
    return r

print(solve(N, T, V))

Solution (Python):
n = int(input())
T = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]
M = []

for i in range(n):
    M += [V[i]]*T[i]*2
   
M = [min(v1, v2) for v1, v2 in zip([0] + M, M + [0])]



for i in range(1,len(M)):
    M[i] = min(M[i],M[i-1]+0.5)
    
for i in range(len(M)-2,0,-1):
    M[i] = min(M[i],M[i+1]+0.5)
    
ans = 0
for i in range(1,len(M)):
    ans += 0.5*(M[i]+M[i-1])*0.5

print(ans)

Solution (Python):
"""
prd_xxx 様のコードを参考にさせていただきました。感謝です...！
https://beta.atcoder.jp/contests/abc076/submissions/1724160
"""

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

maxv = [0]

for v, t in zip(V, T):
    
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t * 2):
        maxv.append(v)

T = len(maxv)

for i in range(T - 1):
    maxv[i + 1] = min(maxv[i+1], maxv[i] + 0.5)

maxv[-1] = 0

for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)

ans = 0

for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)

Solution (Python):
def solve(N, T, V):
    from itertools import accumulate
    ds = [0] + list(accumulate(T))
    vs = [0] + [min(V[i], V[i + 1]) for i in range(len(V) - 1)] + [0]
    for i in range(len(vs)):
        d = ds[i]
        vs[i] = min([v + abs(d - ds[j]) for j, v in enumerate(vs)])
    def calc(t, v0, v1, maxv):
        t0 = maxv - v0
        t1 = maxv - v1
        if t0 + t1 < t:
            return t * maxv - t0 * t0 / 2 - t1 * t1 / 2
        else:
            t0 = (t + v1 - v0) / 2
            t1 = (t + v0 - v1) / 2
            v = (t + v0 + v1) / 2
            S = v * t - t0 * t0 / 2 - t1 * t1 / 2
            return S
    r = 0
    for i in range(N):
        c = calc(T[i], vs[i], vs[i + 1], V[i])
        r += c
    return r
    
if __name__ == '__main__':
    N = int(input())
    T = [int(_) for _ in input().split()]
    V = [int(_) for _ in input().split()]
    print(solve(N, T, V))

Solution (Python):
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
MAX_T = 200
MAX_V = 100
INF = 1e9
index = 0
tsum = 0
T = sum(t)
dp = [[-INF] * (2*MAX_V+1) for i in range(2*T+1)]
dp[0][0] = 0.0
for i in range(2*T):
    if i+1 > 2 * (tsum + t[index]):
        tsum += t[index]
        index += 1
    for j in range(2*MAX_V+1):
        jj = 0.5 * j
        if jj > v[index]:
            continue
        if jj < v[index]:
            dp[i+1][j+1] = max((dp[i+1][j+1], dp[i][j] + 0.5 * jj + 0.125))
        if jj > 0:
            dp[i+1][j-1] = max((dp[i+1][j-1], dp[i][j] + 0.5 * jj - 0.125))
        dp[i+1][j] = max((dp[i+1][j], dp[i][j] + 0.5 * jj))

print(dp[2*T][0])

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)


def solve(N, t, v):
    memo = [0]
    for i in range(len(t)):
        memo += ([v[i]] * (t[i]) * 2)
    memo += [0]

    for i in range(len(memo) - 1):
        memo[i] = min(memo[i], memo[i + 1])

    memo[0] = 0
    for i in range(0, len(memo) - 1):
        memo[i + 1] = min(memo[i + 1], memo[i] + 0.5)

    memo[-1] = 0
    for i in range(len(memo) - 1, 0, -1):
        memo[i - 1] = min(memo[i - 1], memo[i] + 0.5)

    ans = 0
    for i in range(len(memo) - 1):
        ans += (memo[i] + memo[i + 1]) / 4
    return ans


def main():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    print("{0:4f}".format(solve(N, t, v)))


if __name__ == '__main__':
    main()

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

from_start=[0]
for i in range(N):
  for s in range(2*t[i]):
    from_start += [min(from_start[-1]+1, 2*v[i])]

to_goal=[0]
t.reverse()
v.reverse()
for i in range(N):
  for s in range(2*t[i]):
    to_goal += [min(to_goal[-1]+1, 2*v[i])]
to_goal.reverse()
velo=[]
for s in range(2*sum(t)+1):
  velo+=[min(from_start[s],to_goal[s])]
  

print(sum(velo)/4-(velo[0]+velo[-1])/8)

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

time = 0
sum_t = sum(t)
velo_cap =[float("inf")]*(2*sum_t+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum_t+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum_t+1):
  velo_cap[s] = min(velo_cap[s],2*sum_t-s,s)


print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)

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

T=sum(t)
t_len=len(t)

maxv=[0]
for ind_i,i in enumerate(t):
	for j in range(i*2):
		if j==i*2-1:
			if ind_i==t_len-1:
				maxv.append(0)
			else:	
				maxv.append( min(v[ind_i],v[ind_i+1]) )
		else:
			maxv.append(v[ind_i])


for i in range(1,2*T):
	maxv[i]=min(maxv[i],maxv[i-1]+0.5)


for i in reversed(range(1,2*T)):
	maxv[i]=min(maxv[i],maxv[i+1]+0.5)






cnt=0
for i in maxv:
	cnt+=0.5

print sum(maxv)/2

Solution (Python):
N = int(input())
ts = [int(i) for i in input().split()]
vmax = [int(i) for i in input().split()]
s = []

v = 0
for i in range(N):
    v = min(v, vmax[i])
    for t in range(ts[i]):
        if v < vmax[i]:
            s.append(v + 0.5)
            v += 1
        else:
            s.append(v)

ts = ts[::-1]
vmax = vmax[::-1]
s = s[::-1]

v = 0
count = 0
for i in range(N):
    v = min(v, vmax[i])
    for t in range(ts[i]):
        if v < vmax[i]:
            if s[count] == v + 0.5:
                s[count] = v + 0.25
            else:
                s[count] = min(v + 0.5, s[count])
            v += 1
        else:
            s[count] = min(v, s[count])
        count += 1

print(sum(s))

Solution (Python):
def main():
    N = int(input())
    Tn = tuple(map(int, input().split()))
    Vn = tuple(map(int, input().split()))

    t = (0,) + Tn + (0,)
    v = (0,) + Vn + (0,)
    maxv = [0]
    for i in range(1, N + 1):
        if v[i-1] <= v[i] > v[i+1]:
            maxv += [v[i]] * (t[i] * 2 - 1)
        elif v[i-1] > v[i] <= v[i+1]:
            maxv += [v[i]] * (t[i] * 2 + 1)
        else:
            maxv += [v[i]] * t[i] * 2
    maxv += [0]

    cnt = len(maxv)
    for i in range(1, cnt):
        maxv[i] = min(maxv[i], maxv[i-1] + 0.5)

    for i in range(cnt - 2, -1, -1):
        maxv[i] = min(maxv[i], maxv[i+1] + 0.5)

    s = 0
    for i in range(cnt - 1):
        s += (maxv[i] + maxv[i+1]) * 0.5 / 2
    print(s)

main()

Solution (Python):
def get_distance_and_next_speed(current_speed, max_speed, time, next_max_speed):
	
	if max_speed <= next_max_speed and max_speed >= current_speed and max_speed - current_speed <= time:
		
		acceleration_duration = max_speed - current_speed
		max_speed_duration = time - acceleration_duration
		distance = ((max_speed + current_speed) * acceleration_duration) / 2.0 + max_speed_duration * max_speed
		new_current_speed = max_speed
		return distance, new_current_speed, 1
	
	
	elif max_speed <= next_max_speed and max_speed > current_speed and max_speed - current_speed > time:
		
		max_valid_speed = current_speed + time
		distance = (max_valid_speed + current_speed) * time / 2.0
		new_current_speed = max_valid_speed
		return distance, new_current_speed, 2
	
	
	elif max_speed > next_max_speed and max_speed >= current_speed and (max_speed - current_speed) + (max_speed - next_max_speed) <= time:
		
		acceleration_duration = max_speed - current_speed
		acceleration_distance = (max_speed + current_speed) * acceleration_duration / 2.0
		
		
		max_speed_duration = time - ((max_speed - current_speed) + (max_speed - next_max_speed))
		max_speed_distance = max_speed_duration * max_speed
		
		
		deceleration_duration = max_speed - next_max_speed
		deceleration_distance = deceleration_duration * (max_speed + next_max_speed) / 2.0
		
		distance = acceleration_distance + max_speed_distance + deceleration_distance
		new_current_speed = next_max_speed
		return distance, new_current_speed, 3
	
	
	elif max_speed > next_max_speed and max_speed > current_speed and (max_speed - current_speed) + (max_speed - next_max_speed) > time:
		
		if current_speed + time <= next_max_speed:
			distance = (current_speed + current_speed + time) * time / 2.0
			new_current_speed = current_speed + time
			return distance, new_current_speed, 4
		
		
		else:
			acceleration_duration = (next_max_speed - current_speed + time) / 2.0
			deceleration_duration = time - acceleration_duration
			max_valid_speed = current_speed + acceleration_duration
			
			
			acceleration_distance = (max_valid_speed + current_speed) * acceleration_duration / 2.0
			
			
			deceleration_distance = (max_valid_speed + next_max_speed) * deceleration_duration / 2.0
			
			distance = acceleration_distance + deceleration_distance
			new_current_speed = next_max_speed
			return distance, new_current_speed, 4

case_number = input()
time_list = [int(x) for x in raw_input().split()]
velocity_list = [int(x) for x in raw_input().split()]
velocity_list.append(0)	

velocity_list = velocity_list[::-1]
time_list = time_list[::-1]

for vi in xrange(len(velocity_list) - 1):
	cur_v = velocity_list[vi]
	next_v = velocity_list[vi + 1]
	duration_time = time_list[vi]
	next_v = min(next_v, cur_v + duration_time)
	velocity_list[vi + 1] = next_v

velocity_list = velocity_list[::-1]
time_list = time_list[::-1]

CURRENT_SPEED = 0
TOTAL_DISTANCE = 0
DISTANCE_LIST = [0]
SPEED_LIST = [0]

for INDEX in xrange(case_number):
	
	DELTA_DISTANCE, CURRENT_SPEED, STATUS = get_distance_and_next_speed(current_speed = CURRENT_SPEED, max_speed = velocity_list[INDEX], time = time_list[INDEX], next_max_speed = velocity_list[INDEX + 1])
	DISTANCE_LIST.append(DELTA_DISTANCE)
	TOTAL_DISTANCE += DELTA_DISTANCE
	SPEED_LIST.append(CURRENT_SPEED)

print '%.10f' % TOTAL_DISTANCE

Solution (Python):


def f(n, ts, vs):
    sumOfT = sum(ts)

    t = 0
    k = 0
    k1s = [k]

    for i in range(n-1):
        t += ts[i]
        k = min(k, vs[i] - t)
        k1s.append(k)

    t = sumOfT
    k = t
    k2s = [k]

    for i in range(n-1, 0, -1):
        t -= ts[i]
        k = min(k, vs[i] + t)
        k2s.insert(0, k)

    t0 = 0
    d = 0

    for t, v, k1, k2  in zip(ts, vs, k1s, k2s):
        
        
        
        

        t3 = t0 + t

        t1 = v - k1
        t2 = k2 - v
        
        if t1 > t2:
            t1 = (k2 - k1)/2
            t2 = t1

        if t0 < t1:
            t12 = min(t1, t3)
            d +=  k1*(t12-t0) + (t12**2 -t0**2)/2

        dt = min(t2, t3) - max(t0, t1)
        if dt > 0:
            d += v*dt

        if t2 < t3:
            t22 = max(t2, t0)
            d +=  k2*(t3-t22) - (t3**2 - t22**2)/2

        t0 = t3
        
    return d


def test():
    assert(f(1, [100], [30]) == 2100)
    assert(f(2, [60,50], [34,38]) == 2632)
    assert(f(3, [12, 14, 2], [6, 2, 7]) == 76)
    assert(f(1, [9], [10]) == 20.25)
    assert(f(10,[64, 55, 27, 35, 76, 119, 7, 18, 49, 100],[29, 19, 31, 39, 27, 48, 41, 87, 55, 70]) == 20291)


def main():
    n = int(input())
    ts = list(map(int, input().split()))
    vs = list(map(int, input().split()))

    print('{0:.4f}'.format(f(n, ts, vs)))

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):

  ndp = [None]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi = min(len(dp)-1,vf+t)
    while vi >= 0 and dp[vi] is None:
      vi -= 1

    if vi < max(0,vf-t):
      ndp[vf] = None
    else:
      vp = (vf+t+vi)/2
      ndp[vf] = dp[vi] + 2*vp*vp-vf*vf-vi*vi - 2*max(0,vp-v_max)**2
  dp = ndp
 
print(dp[0]/8)

Solution (Python):
N = int(input())
t = list(map(int,input().split()))
T = [0]
tot = 0
for i in range(len(t)):
    tot += t[i]
    T.append(tot)
T = list(map(lambda x: x*2,T))
v = list(map(int,input().split()))
v.append(0)
curv = 0
dist = 0
curt = 0



for i in range(N):
    for _ in range(T[i], T[i+1]):
        prev = curv
        ok = 1
        
            
        for j in range(N-i):
            if T[i+j+1]/2.0 - curt > curv - v[i+j+1]:
                continue
            else:
                ok = 0
                break
        if ok == 1:
            if curv < v[i]:
                curv += 0.5
        elif ok == 0:
            curv -= 0.5
        curt += 0.5
        dist +=(prev+curv) / 4.0




print(dist)

Solution (Python):
N = int(input())
T = [int(x) for x in input().split(' ')]
V = [int(x) for x in input().split(' ')]
V.append(0)
s = sum(T)
time = [s]
for i in range(N):
    s -= T[N - 1 - i]
    time.append(s)
time.reverse()

s = 0
answer = 0.0
for i in range(N):
    t = T[i]
    limit = V[i]
    g = V[i + 1]
    for j in range(i + 2, N + 1):
        if V[j] + time[j] - time[i + 1] < g:
            g = V[j] + time[j] - time[i + 1]
    x = (s + g + t) / 2.0
    if t <= limit - s and g >= limit:
        answer += 0.5 * t * (2.0 * s + t)
        s += t
    elif g >= limit:
        answer += 0.5 * (limit ** 2 - s ** 2) + limit * (t - limit + s)
        s = limit
    elif t <= g - s:
        answer += 0.5 * t * (2.0 * s + t)
        s += t
    elif x >= limit and s - g < t:
        answer += limit ** 2 - 0.5 * (s ** 2 + g ** 2) + limit * (t - 2.0 * limit + s + g)
        s = g
    elif s - g < t:
        answer += x ** 2 - 0.5 * (s ** 2 + g ** 2)
        s = g
    elif s - g == t:
        answer += 0.5 * (s + g) * t
        s = g
    else:
        print("error")
        break

print(answer)

Solution (Python):






from sys import stdin


def solve(ts, vs):
  if len(ts) == 0: return 0.0

  time  = sum(ts)  
  limit = min(vs)  
  if time / 2.0 <= limit:     
    return (time / 2.0) ** 2  

  
  if limit == 0:
    
    vzero = [i for i in range(len(vs)) if vs[i] == 0][0]
    return solve(ts[:vzero],     vs[:vzero]) + \
           solve(ts[vzero + 1:], vs[vzero + 1:])

  
  ts[0]  -= 1
  ts[-1] -= 1
  
  if ts[-1] == 0:
    ts = ts[:-1]
    vs = vs[:-1]
  if ts[0] == 0:
    ts = ts[1:]
    vs = vs[1:]
  
  vs = [v - 1 for v in vs]
  
  dist = time - 2 + 1
  return dist + solve(ts, vs)


def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N = int(stdin.readline())
ts = splitToInt(stdin.readline())
vs = splitToInt(stdin.readline())
if len(ts) != N or len(vs) != N: raise
print(solve(ts, vs))

Solution (Python):
n = int(input())
t = list(map(int,input().split()))
runt = sum(t)

t.append(0)
for i in range(n):
    t[i+1] += t[i]

v = list(map(int,input().split()))
v.append(0)
det = [v[i]+t[i-1] for i in range(1,n+1)]

runlen = 0.0
vnow = 0.0
idx = 0
for se in range(2*runt):
    now = se/2
    if t[idx] == now:
        idx += 1
    lim = min(det[idx:])
    if - lim + now + vnow == 0.0:
        vnow -= 0.5
        runlen += vnow*0.5 + 0.25
    elif v[idx] == vnow:
        runlen += vnow*0.5
    else:
        vnow += 0.5
        runlen += vnow*0.5 - 0.25
print(runlen)

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

maxv = [0]
for v,t in zip(vs,ts):
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t*2):
        maxv.append(v)
T = len(maxv)

for i in range(T-1):
    maxv[i+1] = min(maxv[i+1], maxv[i] + 0.5)

maxv[-1] = 0
for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i+1] + 0.5)

ans = 0.0
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)

Solution (Python):






from sys import stdin


def solve(ts, vs):
  if len(ts) == 0: return 0.0

  time  = sum(ts)  
  limit = min(vs)  
  if time / 2.0 <= limit:     
    return (time / 2.0) ** 2  

  
  if limit == 0:
    
    vzero = [i for i in range(len(vs)) if vs[i] == 0][0]
    return solve(ts[:vzero],     vs[:vzero]) + \
           solve(ts[vzero + 1:], vs[vzero + 1:])

  
  n = len(ts)
  ts[0]     -= 1
  ts[n - 1] -= 1
  
  if ts[n - 1] == 0:
    ts = ts[:n - 1]
    vs = vs[:n - 1]
  if ts[0] == 0:
    ts = ts[1:]
    vs = vs[1:]
  
  vs = [v - 1 for v in vs]
  
  dist = time - 2 + 1
  return dist + solve(ts, vs)


def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N = int(stdin.readline())
ts = splitToInt(stdin.readline())
vs = splitToInt(stdin.readline())
if len(ts) != N or len(vs) != N: raise
print(solve(ts, vs))

Solution (Python):
n = int(input())

tt = list(map(int, input().split()))
v = list(map(int, input().split()))

time = sum(tt);
INF = 999999
border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
	temp += tt[i]
	border[i+1] = temp
	start_v[i] = v[i]
	end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0
new_interval = False
limitation_front =0 


while t < time :
	t += 0.5
	new_interval = False

	
	v0 = v[idx]
	if t == border[idx+1]:
		idx += 1
		new_interval = True


	if(not new_interval):
		limitation_front += 0.5
		if v0 > limitation_front:
			v0 = limitation_front
	
	if new_interval: 
		limitation_front = INF
		for j in range(n+1):
			if border[j] <= t:
				
				temp = end_v[j] + (t - border[j])
				if v0 > temp:
					v0 = temp
				if limitation_front > temp:
					limitation_front = temp
			else:
				break
			


	for j in range(n+1):
		if border[j] >= t:
			
			temp = start_v[j] + (border[j] - t)
			if v0 > temp:
				v0 = temp

	


	ans += (vlast + v0)
	vlast = v0

ans /= 4.0
print (ans)

Solution (Python):


from itertools import chain

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

vm = list(chain.from_iterable([v] * (2 * t) for t, v in zip(ts, vs)))
vm = [min(v1, v2) for v1, v2 in zip([0] + vm, vm + [0])]
T = len(vm)

for i in range(T - 1):
    vm[i + 1] = min(vm[i + 1], vm[i] + 0.5)

for i in range(T - 1)[::-1]:
    vm[i] = min(vm[i], vm[i + 1] + 0.5)

print(sum((v1 + v2) / 4 for v1, v2 in zip(vm, vm[1:])))

Solution (Python):
def D_AtCoder_Express(N, T, V):
    """
    N:時間の区間の総数
    T:各時間区間の秒数
    V:各時間区間において許される最大速度
    """
    from itertools import chain

    
    
    speed = list(chain.from_iterable([v] * (2 * t) for t, v in zip(T, V)))

    
    speed = [min(v1, v2) for v1, v2 in zip([0] + speed, speed + [0])]
    length = len(speed)

    
    
    speed_previous = 0  
    for current in range(1, length):
        speed[current] = speed_previous = min(
            speed[current], speed_previous + 0.5)

    
    speed_previous = 0
    for current in range(length - 1, 0, -1):
        speed[current] = speed_previous = min(
            speed[current], speed_previous + 0.5)

    
    
    return sum((v1 + v2) * 0.5 / 2 for v1, v2 in zip(speed, speed[1:]))

N = int(input())
T = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]
print(D_AtCoder_Express(N, T, V))

Solution (Python):
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split())) + [0]

    CT = [0 for x in range(N+1)]  
    M = [float('inf') for x in range(len(T))]

    count = 0
    ct = 0
    for t, v in zip(T, V[:N]):
        CT[count] = ct
        ct += t
        count += 1
    CT[N] = ct

    for n in range(N):
        for i in range(n+1):
            M[i] = min(M[i], V[n+1] + (CT[n+1] - CT[i]))


    now = 0
    S = 0
    for q in range(len(T)):
        future = M[q]
        restriction = V[q]
        for s in range(T[q]*2):
            future -= 0.5
            pnow = now
            now = min(min(future, restriction), now + 0.5)
            S += (now + pnow)/4

    print(S)

if __name__ == "__main__":
    main()

Solution (Python):

n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]


dt=[0 for i in range(n)] 
v0=[0 for i in range(n)] 
ve=[0 for i in range(n)] 
S=[0 for i in range(n)] 
ok=0 



for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        dt[i]=t[i]
        ve[i]=min(v[i+1],v[i],v0[i]+dt[i])



while ok==0:
    for i in range(n-1):
        if  abs((ve[i+1]-v0[i+1])/dt[i+1]) >1:
                ve[i]=ve[i]-1
                v0[i+1]=v0[i+1]-1

                break
    else:
        ok=1



for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 

    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)


print(sum(S))

Solution (Python):
n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(n)]
S1=[0 for i in range(n)]
S2=[0 for i in range(n)]
vel=[0 for i in range(n)]

dt=[0 for i in range(n)]
v0=[0 for i in range(n)]
ve=[0 for i in range(n)]
ok=0



for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        dt[i]=t[i]
        ve[i]=min(v[i+1],v[i],v0[i]+dt[i])





while ok==0:
    for i in range(n-1):

        if  abs((ve[i+1]-v0[i+1])/dt[i+1]) >1:
                ve[i]=ve[i]-1
                v0[i+1]=v0[i+1]-1




                break
    else:
        ok=1







for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=(ttt-v[i]+v0[i])*(vvv-v[i]) 
    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=0

print(sum(S))

Solution (Python):
n = input()
t = map(int, raw_input().split())
v = map(int, raw_input().split())
t = [2 * i for i in t]
v = [2 * i for i in v]
f = [1000 for i in range(sum(t) + 1)]

s = 0
for i in range(n):
	for j in range(s, s + t[i] + 1):
		f[j] = min(f[j], v[i])
	s += t[i]
f[0] = 0
f[s] = 0

for i in range(1, s + 1):
	f[i] = min(f[i], f[i - 1] + 1)

for i in range(s)[::-1]:
	f[i] = min(f[i], f[i + 1] + 1)

print (sum(f[:-1]) + sum(f[1:])) / 8.0

Solution (Python):
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
vs.append(0)

ss = [ts[0]]
for i in range(1, n):
    ss.append(ss[-1])
    ss[-1] += ts[i]

ds = [[-1 for _ in range(101)] for _ in range(2)]
ds[0][0] = 0
i = 0
for t in range(1, ss[-1] + 1):
    vl = vs[i]
    ve = vs[i]
    if t == ss[i]:
        i += 1
        ve = min(ve, vs[i])
    for v in range(101):
        ds[t % 2][v] = -1
        if 0 <= ds[(t - 1) % 2][v]:
            if v < vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + 4 * v + 1
            elif v == vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + 4 * v
    for v in range(1, 101):
        if 0 <= ds[(t - 1) % 2][v] and v <= vl and v - 1 <= ve:
            ds[t % 2][v - 1] = max(ds[t % 2][v - 1], ds[(t - 1) % 2][v] + 4 * v - 2)
    for v in range(100):
        if 0 <= ds[(t - 1) % 2][v] and v < vl and v + 1 <= ve:
            ds[t % 2][v + 1] = max(ds[t % 2][v + 1], ds[(t - 1) % 2][v] + 4 * v + 2)

print(ds[ss[-1] % 2][0] / 4)

Solution (Python):

def spaceinput():
    return list(map(int,input().split(" ")))

def interval(t):
    pass

N=int(input())
T=spaceinput()
v=spaceinput()

Tmax=0

for i in range(N):
    Tmax+=(T[i])

mv={}

frange=[x for x in range(2*Tmax+1)]

k=0
sT=T[0]
d=0.5

mv[0]=0
for t in [x/2 for x in range(1,2*Tmax)]:

    if sT<t:
        k+=1
        if k<len(T):
            sT+=T[k]
        else:
            break

    mv[t]=min(v[k],mv[t-0.5]+d)

mv[Tmax]=0

k=N-1
sT=Tmax-T[-1]
for t in reversed([x/2 for x in range(1,2*Tmax)]):
    if sT>t:
        k-=1
        sT-=T[k]

    mv[t]=min(v[k],mv[t],mv[t+d]+d)


res=0
k=0
sT=T[0]
for t in [x/2 for x in range(1,2*Tmax)]:
    if sT<t:
        if t==Tmax-1:
            break
        k+=1
        if k<len(T):
            sT+=T[k]
    res+=mv[t]*0.5

print(res)

Solution (Python):
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
ans = 0

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))

Solution (Python):
n = int(input())
t_list = input().split()
t_list = [int(t) for t in t_list]
v_list = input().split()
v_list = [int(v) for v in v_list]


down_list = []
v_list.append(0)
for i in range(n):
    down = []
    down.append(sum(t_list[:i+1]))
    down.append(min(v_list[i],v_list[i+1]))
    down_list.append(down)
    
now_v = 0
distance = 0
kukan = 0
down_check = 0
now_s = 0
last_time = down_list[-1][0]
while now_s < last_time:
    for down in down_list[kukan:]:
        if down[1]+(down[0]-now_s)*1==now_v:
            next_s = down_list[kukan][0]
            next_v = now_v +(-1*(next_s-now_s))

            distance += (next_v +now_v) * (next_s-now_s) /2

            now_v = next_v
            now_s = next_s
            kukan += 1
            down_check = 1
            break
    if down_check == 1:
        down_check = 0
        continue
    else:
        if now_v == v_list[kukan]:
            distance += now_v * 0.5

        else:
            next_v = now_v + 0.5
            distance += (next_v + now_v) * 0.5 /2

            now_v = next_v

        now_s += 0.5
        if kukan < len(down_list):
            if now_s == down_list[kukan][0]:
                kukan += 1


print(distance)

Solution (Python):
from itertools import chain

n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))

va = list(chain.from_iterable([v] * (2 * t) for t, v in zip(ts, vs)))
va = [min(v1, v2) for v1, v2 in zip([0] + va, va + [0])]
lt = len(va)
va[-1] = 0

pv = 0
for ct in range(1, lt):
    va[ct] = pv = min(va[ct], pv + 0.5)

pv = 0
for ct in range(lt - 1, 0, -1):
    va[ct] = pv = min(va[ct], pv + 0.5)

print(sum((v1 + v2) / 4 for v1, v2 in zip(va, va[1:])))

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

vs.append(0)

for i in xrange(N-1, -1, -1):
  vs[i] = min(vs[i], vs[i+1] + ts[i])

def dist(vstart, vend, time):
  return time * (min(vstart, vend) + (abs(vstart - vend) / 2.0))

v = 0
ans = 0.0
for i in xrange(N):
  a = min(ts[i], vs[i] - v)
  vs[i] = min(vs[i], v + a)
  b = max(0, vs[i] - vs[i+1]) 
  c = ts[i] - a - b
  

  if c >= 0:
    ans += dist(v, vs[i], a) + dist(vs[i], vs[i], c) + dist(vs[i], vs[i+1], b)
  else:
    a, b = (a-b+ts[i])/2.0, (b-a+ts[i])/2.0
    ans += dist(v, v+a, a) + dist(v+a, v+a-b, b)

  v = v + a - b

print ans