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())
inl=list(map(lambda x: int(x)*2,input().split()))
vs=list(map(int,input().split()))

sumtime = sum(inl)

limits = [0]
for i, t in enumerate(inl):
    for _ in range(t):
        limits.append(vs[i])

resv = [0]
for i in range(1, sumtime+1):
    resv.append(min(resv[-1]+0.5, limits[i]))

resv[sumtime] = 0
for i in reversed(range(1, sumtime+1)):
    resv[i-1] = min(resv[i]+0.5, resv[i-1], limits[i])



res = 0.0
for i in range(sumtime):
    res += (resv[i] + resv[i+1])*0.5

print(res*0.5)

Solution (Python):
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
def exe(x, y, z, t):
  ans = t * y
  if x < y:
    ans -= (y - x) * (y - x) / 2
  if y > z:
    ans -= (y - z) * (y - z) / 2
  return ans

def upd(x, y, z, t):
  a = y - x
  b = y - z
  if y > z:
    if t < a:
      y = x + t
    elif t < a + b:
      y = x + (t + (z - x)) / 2
  else:
    if t < a:
      y = x + t
  return y

v = [0] + v + [0]
L = [0] * len(v)
v[1] = upd(v[0], v[1], v[2], t[0])
v[-2] = upd(v[-1], v[-2], v[-3], t[-1])
for i in range(1, N):
  k = -1
  for j in range(1, N + 1):
    if L[j] == 0:
      if k == -1:
        k = j
      else:
        if v[j] < v[k]:
          k = j
  L[k] = 1
  if k != 1:
    v[k - 1] = upd(min(v[k], v[k - 2]), v[k - 1], max(v[k], v[k - 2]), t[k - 2])
  if k != N:
    v[k + 1] = upd(min(v[k], v[k + 2]), v[k + 1], max(v[k], v[k + 2]), t[k])

ans = 0
for i in range(N):
  ans += exe(v[i], v[i + 1], v[i + 2], t[i])

print(ans)

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

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

tl = []
v1 = [0]+v+[0]
ts = 0
for i in range(N+1):
    tl.append([ts,min(v1[i],v1[i+1])])
    if i!=N:
        ts+=t[i]

max_v = []

k = 0
for i in range(2*ts+1):
    mv = 10**27
    if tl[k+1][0]<i/2:
        k+=1
    for j in range(len(tl)):
        mv = min(mv,abs(i/2-tl[j][0])+tl[j][1],v[k])
    max_v.append(mv)
s = 0
for i in range(2*ts):
    s+=max_v[i]+max_v[i+1]

print(s/4)

Solution (Python):

def main():
    buf = input()
    N = int(buf)
    buf = input()
    buflist = buf.split()
    t = list(map(int, buflist))
    buf = input()
    buflist = buf.split()
    v = list(map(int, buflist))
    t.append(0)
    v.append(0)
    for i, _ in enumerate(t): 
        t[i] *= 2
        v[i] *= 2
    time = 0
    last_speed = 0
    speed = 0
    distance = 0.0
    point = 0
    spd_time_list = []
    for i, _ in enumerate(t):
        spd_time_list.append((v[i], (0 if not spd_time_list else t[i-1] + spd_time_list[-1][1])))
    while time < spd_time_list[-1][1]:
        last_speed = speed
        brake = False
        for i in range(point+1, len(spd_time_list)):
            if speed >= spd_time_list[i][0] + (spd_time_list[i][1] - time):
                brake = True
                break
        if brake:
            speed -= 1
        elif speed < spd_time_list[point][0]:
            speed += 1
        distance += (last_speed + speed) / 2
        time += 1
        if time >= spd_time_list[point+1][1]:
            point += 1
    distance /= 4 
    print(distance)

if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
S=sum(T)
v=[0]*(sum(T)*2+1)
def f(x,l,r,vmax):
    if x<l:
        return vmax+(l-x)
    elif l<=x<=r:
        return vmax
    else:
        return vmax+(x-r)
for i in range(S*2+1):
    l=0
    r=0
    v[i]=f(i*0.5,l,r,0)
    for j in range(N):
        r+=T[j]
        v[i]=min(v[i],f(i*0.5,l,r,V[j]))
        l=r

    v[i]=min(v[i],f(i*0.5,l,r,0))
ans=0
for i in range(S*2):
    ans+=(v[i+1]+v[i])*0.25
print(ans)

Solution (Python):
N = int(raw_input())
ts = map(int, raw_input().split(" "))
vs = map(int, raw_input().split(" "))
tsa = [0]
for t in ts:
    tsa.append(tsa[-1]+t)

T = 0
X = 0
V = 0
def acc():
    ppp = False
    for j in range(N):
        if tsa[j] <= T:
            continue
        if vs[j] > V:
            continue
        c = tsa[j] - T - (V - vs[j])
        if c <= 0:
            return -1
        d = tsa[j] - (T+1) - (V+1 - vs[j])
        if d < 0:
            ppp = True
    if tsa[-1] - T - (V - 0)<=0:
        return -1
    if tsa[-1] - (T+1) - (V+1 - 0) < 0:
        ppp = True
    if ppp:
        return 0
    return 1

def tind():
    for i in range(len(ts)):
        if tsa[i] <= T and  T < tsa[i+1]:
            return i

for i in range(sum(ts)):
    a = acc()
    ti  = tind()
    if a == 1:
        if V == vs[ti]:
            X += V
        else:
            X += V + 0.5
            V += 1
    elif a == 0:
        if V == vs[ti]:
            X += V
        else:
            X += V + 0.25
    else:
        X += V - 0.5
        V -= 1
    T=i+1

print X

Solution (Python):
N = int(input())
t = [0] + [int(x) for x in input().split()]
v = [0] + [int(x) for x in input().split()]

max_speed_from_left = [0] * (N+1) 
max_speed_from_right = [0] * (N+1) 

for i in range(1,N):
  start = max_speed_from_left[i-1]
  max_speed_from_left[i] = min(start + t[i], v[i], v[i+1])
  
for i in range(N-1,0,-1):
  start = max_speed_from_right[i+1]
  max_speed_from_right[i] = min(start + t[i+1], v[i], v[i+1])

speed = [min(x,y) for x,y in zip(max_speed_from_left,max_speed_from_right)]

def dist(left_speed,right_speed,t,v):
  x = (v - left_speed) + (v - right_speed)
  if x >= t:
    v = (left_speed + right_speed + t)/2
    x = t
  
  d = (left_speed + v) * (v-left_speed)/2
  d += v*(t-x)
  d += (right_speed + v) * (v-right_speed)/2
  return d

answer = 0
for i in range(1,N+1):
  answer += dist(speed[i-1],speed[i],t[i],v[i])
print(answer)

Solution (Python):
N=int(input())
t=list(map(int, input().split()))
v=list(map(int, input().split()))
T=sum(t)
V=[0]*(T+2)
from collections import deque
q=[deque() for i in range(101)]
s=0
for i in range(N):
    temp=min(V[s],v[i])
    q[temp].append(s)
    for j in range(t[i]):
        V[s+j+1]=v[i]
    s+=t[i]
q[0].append(T)
vans=[-1]*(T+1)
for i in range(101):
    while(len(q[i])>0):
        s=q[i].popleft()
        if vans[s]==-1:
            vans[s]=i
        if s>0 and vans[s-1]==-1:
            if V[s]>i:
                q[i+1].append(s-1)
            else:
                q[i].append(s-1)
        if s<T and vans[s+1]==-1:
            if V[s+1]>i:
                q[i+1].append(s+1)
            else:
                q[i].append(s+1)
ans=0
for i in range(T):
    if vans[i+1]>vans[i]:
        ans+=vans[i]+0.5
    elif vans[i+1]<vans[i]:
        ans+=vans[i+1]+0.5
    elif V[i+1]>vans[i]:
        ans+=vans[i]+0.25
    else:
        ans+=vans[i]
print(ans)

Solution (Python):
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

T = np.array(T).cumsum()
V = np.array(V)

va = []
i = 0
for t in np.arange(0, T[-1], 0.5):  
    if t < T[i]:
        va.append(V[i])
    else:
        i += 1
        va.append(min(V[i], V[i - 1]))
va.append(0)

v = 0
for i in range(len(va)):
    va[i] = min(va[i], v)
    v = va[i] + 0.5
v = 0
for i in reversed(range(len(va))):
    va[i] = min(va[i], v)
    v = va[i] + 0.5

print((np.array(va) / 2).sum())

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

tli = [ int(it)*2 for it in input().split() ]
vli = [ int(it)*2 for it in input().split() ]

vmax = [0]
for i in range(len(tli)):
  tmp = vmax.pop()
  vmax.append( min(tmp,vli[i]) )
  vmax.extend( [vli[i]]*(tli[i]) )
vmax[-1]=(0)
vmax[0]=0
T = len( vmax ) - 1

for j in range( 1000 ):
  for i in range( T ):
    vmax[i+1] = min( vmax[i]+1 , vmax[i+1] )
  for i in range( T,0,-1):
    vmax[i-1] = min( vmax[i]+1 , vmax[i-1] )
  if (j==0):
    pass
    
    
print ( 0.25 * sum(vmax) )

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

cumsum_t = [0]*(n+1)
for i in range(n):
    cumsum_t[i+1] = cumsum_t[i] + t[i]

v_max = [0]*(2*sum(t) + 1)
for i in range(len(cumsum_t) - 1):
    for j in range(2*cumsum_t[i], 2*cumsum_t[i+1]):
        v_max[j] = v[i]
for i in range(len(cumsum_t) - 1):
    v_max[cumsum_t[i+1]*2] = min(v_max[cumsum_t[i+1]*2], v[i])

speed = [101]*(2*sum(t) + 1)
speed[0] = 0
speed[-1] = 0
for i in range(len(speed) - 1):
    speed[i+1] = min(speed[i+1], speed[i] + 0.5, v_max[i+1])
for i in range(len(speed) - 1)[::-1]:
    speed[i] = min(speed[i], speed[i+1] + 0.5, v_max[i])

print(sum(speed)/2)

Solution (Python):
n = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
kukan = [(0,0,0)]
for i in range(n):
    kukan.append((kukan[i][1],kukan[i][1]+t[i]*2,v[i]))
kukan.append((T,T,0))
vt = [[1000]*(len(kukan)) for _ in range(T+1)]
k = 0
for ts,te,v_ in kukan:
    for i in range(ts,te+1):
        vt[i][k] = v_
    for i in range(ts-1,-1,-1):
        vt[i][k] = vt[i+1][k]+0.5
    for i in range(te+1,T+1):
        vt[i][k] = vt[i-1][k]+0.5
    k += 1
ans = 0
d = [0]*len(vt)
for i in range(len(vt)):
    d[i] = min(vt[i])
for i in range(1,len(vt)):
    ans += (d[i]+d[i-1])*0.25
print(ans)

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

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

N = len(maxv)
candv = [0] * N
for i in range(N - 1):
  candv[i + 1] = min(candv[i] + 0.5, maxv[i + 1])

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

ans = 0
for x1, x2 in zip(candv, candv[1:]):
  ans += (x1 + x2) * 0.5 / 2

print(ans)

Solution (Python):
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min((i/2),((T-i)/2)) for i in range(T+1)]
ts = 0
te = 0
for i,ti in enumerate(t):
    te += ti*2
    vi = v[i]
    for j in range(ts,te):
        vt[j] = min(vt[j],vi)
    for j in range(te,T):
        if vt[j] >= (j-te)/2 + vi:
            vt[j] = (j-te)/2 + vi
        else:
            break
    for j in range(ts-1,-1,-1):
        if vt[j] >= -(j-ts)/2 + vi:
            vt[j] = -(j-ts)/2 + vi
        else:
            break
    ts = te
print(sum(vt)/2)

Solution (Python):
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [(i/2) if i<T/2 else ((T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i,ti in enumerate(t):
    te += ti*2
    vi = v[i]
    for j in range(ts,te):
        vt[j] = min(vt[j],vi)
    for j in range(te,T):
        if vt[j] >= (j-te)/2 + vi:
            vt[j] = (j-te)/2 + vi
        else:
            break
    for j in range(ts-1,-1,-1):
        if vt[j] >= -(j-ts)/2 + vi:
            vt[j] = -(j-ts)/2 + vi
        else:
            break
    ts = te
print(sum(vt)/2)

Solution (Python):
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    for j in range(T+1):
        vt[j] = min(vt[j],v[i]+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    t = f()
    v = f()
    


    sumt = sum(t)*2
    vs = [100000000] * (sumt+1)

    vs[0] = 0

    for i in range(1,sumt):
        totalt = 0
        idx = 0
        for k in range(n):
            totalt += t[k]*2
            if totalt >= i:
                idx = k
                break

        vs[i] = min(vs[i-1]+0.5, v[idx])

    vs[sumt] = 0
    for i in range(sumt-1, 0, -1):
        totalt = 0
        idx = 0
        for k in range(n):
            totalt += t[k]*2
            if totalt >= i+1:
                idx = k
                break

        vs[i] = min(vs[i+1]+0.5, vs[i], v[idx])

    ans = 0
    for i in range(sumt):
        ans += (vs[i]+ vs[i+1])/4


    
    print(ans)

solve()

Solution (Python):

import sys
import numpy as np


def solve(N: int, T: "List[int]", V: "List[int]"):
    t_period = [0 for i in range(N+1)]
    for i in range(N):
        t_period[i+1] = t_period[i] + T[i]*2

    V = [0] + V + [0]
    limit = np.zeros((N+2,t_period[N]+1))
    line = np.arange(0, t_period[N]/2+0.5, 0.5)
    for i in range(N+2):
        if i == 0:
            l, r = 0, 0
        elif i == N+1:
            l, r = t_period[N], t_period[N]
        else:
            l, r = t_period[i-1], t_period[i]
        limit[i] = np.max([-line + l * 0.5, line * 0, line - r * 0.5], axis=0) + V[i]
    speed = np.min(limit, axis=0)

    total = 0
    for t in range(t_period[N]):
        total += (speed[t] + speed[t+1]) * 0.5 * 0.5

    print(total)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    t = [ int(next(tokens)) for _ in range(N) ]  
    v = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, t, v)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import numpy as np


def solve(N: int, T: "List[int]", V: "List[int]"):
    t_period = [0 for i in range(N+1)]
    for i in range(N):
        t_period[i+1] = t_period[i] + T[i]*2

    limit = np.zeros((t_period[N]+1,))
    for i in range(1, N):
        limit[t_period[i]] = min((V[i-1], V[i]))
    for i in range(N):
        limit[t_period[i]+1:t_period[i+1]] = V[i]
    
    speed = np.zeros((t_period[N]+1,))

    for v in range(1, 201):
        speed[v:t_period[N]+1-v] = np.min(
            [limit[v:t_period[N]+1-v], speed[v-1:t_period[N]-v]+0.5, speed[v+1:t_period[N]+2-v]+0.5],
            axis=0
            )

    total = 0
    for t in range(t_period[N]):
        total += (speed[t] + speed[t+1]) * 0.5 * 0.5
    
    print(total)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    t = [ int(next(tokens)) for _ in range(N) ]  
    v = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, t, v)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import numpy as np


def solve(N: int, T: "List[int]", V: "List[int]"):
    t_period = [0 for i in range(N+1)]
    for i in range(N):
        t_period[i+1] = t_period[i] + T[i]*2

    limit = np.zeros((t_period[N]+1,))
    for i in range(1, N):
        limit[t_period[i]] = min((V[i-1], V[i]))
    for i in range(N):
        limit[t_period[i]+1:t_period[i+1]] = V[i]
    
    speed = np.zeros((t_period[N]+1,))

    for v in range(1, 201):
        speed[1:t_period[N]] = np.min([limit[1:t_period[N]], speed[0:t_period[N]-1]+0.5, speed[2:t_period[N]+1]+0.5], axis=0)

    total = 0
    for t in range(t_period[N]):
        total += (speed[t] + speed[t+1]) * 0.5 * 0.5
    
    print(total)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    t = [ int(next(tokens)) for _ in range(N) ]  
    v = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, t, v)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
 
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))

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

timelistsize=len(MAX_V)
REAL_V=[0]*timelistsize


for i in range(1,timelistsize):
  REAL_V[i]=min(REAL_V[i-1]+0.5,MAX_V[i])


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



answer=0
for i in range(timelistsize-1):
  answer+=((REAL_V[i]+REAL_V[i+1])*0.5/2)
print(answer)

'''
tsum=np.sum(t)
print(tsum)
 
Ruisekit=[t[0]]
 
for i in range(1,N):
  Ruisekit.append(t[i]+Ruisekit[i-1])
  
print(Ruisekit)
 
 
 
 
downstart=[]
 
for i in range(N-1):
  if v[i]>v[i+1]:
    downstart.append(t[i]-(v[i]-v[i+1]))
 
print(downstart)
 
velocity=0
downindex=0
 
if downstart:
  nextdownstarttime=downstart[downindex]
 
state='up'
upstarttime=0
upstartspeed=0
answer=0
maxspeed=v[0]
maxspeedindex=0
 
for time in range(1,tsum+1):
  if state=='up':
    velocity+=1
    
    
  if state=='down':
    velocity-=1
  if time==nextdownstarttime:
    if state=='plane':
      answer+=(time-planestarttime)*speed
    state='down'
    print(state)
    downstarttime=time
    downstartspeed=speed
    downindex+=1
    if downindex<len(downstart):
      nextdownstarttime=downstart[downindex]
  if time==Ruisekit[maxspeedindex]:
    maxspeedindex+=1
    if maxspeedindex<len(v):
      maxspeed=v[maxspeedindex]
  if velocity==maxspeed and state!='plane':
    if state=='up':
      answer+=(time-upstarttime)*(velocity-upstartspeed)*0.5
      answer+=(time-upstarttime)*upstartspeed
    if state=='down':
      answer+=(time-downstarttime)*(downstartspeed-velocity)*0.5
      answer+=(time-downstarttime)*downstartspeed
    
    state='plane'
    planestarttime=time
    speed=velocity
    
  print(answer,time,maxspeed,velocity,state)
'''

Solution (Python):
def f(x,l,r,v):
    if 0<=x<=l:
        return v+(l-x)
    if l<=x<=r:
        return v
    if r<=x:
        return v+x-r
def speed(t):
    num=10**9
    for l,r,v in table:
        num=min(num,f(t,l,r,v))
    return num
N=int(input())
T=[int(i) for i in input().split()]
V=[int(i) for i in input().split()]
X=[0]*(N+1)
for i in range(1,N+1):
    X[i]=X[i-1]+T[i-1]
table=[(X[i] , X[i+1],V[i]) for i in range(N)]
table.append((0,0,0))
table.append((X[-1],X[-1],0))

s=speed(0)
meter=0
for i in range(1,2*X[-1]+1):
    t=speed(i*0.5)
    meter+=(s+t)*(0.25)
    s=t
print(meter)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

def add_sentinel(t: list, v: list):
    t = [0] + [0] + t + [t[-1]]
    v = [0] + v + [0]
    return t,v
    
def find_max_vel(ti: int, v: list, intervals: list):
    ret = float('inf')
    for inti, interval in enumerate(intervals):
        st, ed = interval
        
        if ti < st:
            ret = min(ret, v[inti] + (st - ti))
        elif st <= ti <= ed:
            ret = min(ret, v[inti])
        else:
            ret = min(ret, v[inti] + (ti - ed))
            
    return ret

n = ni()
t = list(li())
v = list(li())

t,v = add_sentinel(t, v)
t = list(accumulate(t))
intervals = [(st, ed) for st, ed in zip(t[:-1], t[1:])]

vels = []
for ti in range(2*max(t)+1):
    timestamp = ti/2
    vels.append(find_max_vel(timestamp, v, intervals))
    
ans = 0
for left, right in zip(vels[:-1], vels[1:]):
    ans += (left + right) * 0.5 * 0.5
    
print(ans)

Solution (Python):




n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
sum_t = sum(ts)
n = 2*sum_t+1
max_v = [float("inf")]*n

for i in range(n):
    max_v[i] = min(i/2, (sum_t-i/2))



t_cnt = 0
for t, v in zip(ts, vs):
    for j in range(2*t+1):
        max_v[t_cnt + j] = min(max_v[t_cnt + j], v)

    
    left = t_cnt
    while left >= 0:
        v_left = v + (t_cnt - left)/2
        if max_v[left] < v_left:
            break
        max_v[left] = v_left
        left -= 1
    
    t_cnt += 2*t
    right = t_cnt
    while right < n:
        v_right = v + (right - t_cnt)/2
        if max_v[right] < v_right:
            break
        max_v[right] = v_right
        right += 1


ans = sum(max_v) - (max_v[0]+max_v[-1])/2
print(ans/2)

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


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


N = len(MAX_V)
Feasible_V = [0] * N
for i in range(N - 1):
    Feasible_V[i + 1] = min(Feasible_V[i] + 0.5, MAX_V[i + 1])

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


ans = 0
for i in range(N - 1):
    x1, x2 = Feasible_V[i], Feasible_V[i + 1]
    ans += (x1 + x2) * 0.5 / 2

print(ans)

Solution (Python):







inf=1<<60
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
csum=0
left=[0]*(N+2)
right=[0]*(N+2)
for i in range(N):
    csum+=T[i]
    left[i+2]=csum
    right[i+1]=csum
right[N+1]=right[N]
speed=[0]+V+[0]

def calc(idx):
    l=inf
    r=inf
    for i in range(0,idx):
        
        
        
        l=min(l,speed[i]+(left[idx]-right[i]))
        r=min(r,speed[i]+(right[idx]-right[i]))
    for i in range(idx+1,N+2):
        l=min(l,speed[i]+(left[i]-left[idx]))
        r=min(r,speed[i]+(left[i]-right[idx]))
    l=min(l,speed[idx])
    r=min(r,speed[idx])
    width=right[idx]-left[idx]
    d=0
    
    if (speed[idx]-l)+(speed[idx]-r)<=width:
        d+=(speed[idx]+l)*(speed[idx]-l)/2
        d+=(speed[idx]+r)*(speed[idx]-r)/2
        d+=(speed[idx])*(width-(speed[idx]-l)-(speed[idx]-r))
    elif l<r:
        d+=(l+r)*(r-l)/2
        d+=(width-(r-l))*(r+r+(width-(r-l))/2)/2
    else:
        d+=(l+r)*(l-r)/2
        d+=(width-(l-r))*(l+l+(width-(l-r))/2)/2
    return d

ans=0
for i in range(1,N+1):
    ans+=calc(i)
print(ans)

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

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

def dist(i):
    lspeed = z[i]
    rspeed = z[i+1]
    ta = v[i] - lspeed
    tb = v[i] - rspeed
    if ta + tb <= t[i]: 
        c = (lspeed+v[i])*ta/2 + v[i]*(t[i]-ta-tb) + (rspeed+v[i])*tb/2
    else: 
        a = (rspeed+t[i]-lspeed)/2
        c = (2*lspeed+a)*a/2 + (lspeed+a+rspeed)*(t[i]-a)/2
    return c

ans=0
for i in range(0,n):
    ans += dist(i)

print(ans)

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

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

def dist(i,first): 
    ta = v[i] - first
    tb = v[i] - maxspeed[i+1]
    if ta + tb <= t[i]:
        c = (first+v[i])*ta/2 + v[i]*(t[i]-ta-tb) + (maxspeed[i+1]+v[i])*tb/2
        lastspeed = maxspeed[i+1]
    elif maxspeed[i+1] - first > t[i]:
        c = (first + first + t[i])*t[i]/2
        lastspeed = first + t[i]
    else:
        a = (maxspeed[i+1]+t[i]-first)/2
        c = (first+first+a)*a/2 + (first+a+maxspeed[i+1])*(t[i]-a)/2
        lastspeed = maxspeed[i+1]
    return c, lastspeed


ans = 0
firstspeed = 0
for i in range(n):
    d,firstspeed = dist(i,firstspeed)
    ans += d

print(ans)

Solution (Python):

import sys, collections, bisect, math, itertools
from fractions import gcd 
input = sys.stdin.readline 

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

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





def dist(first,i): 
    ti = t[i]
    vi = v[i]
    mi1= maxspeed[i+1]
    ta = vi - first
    tb = vi - mi1
    if ta + tb <= ti:
        c = (first+vi)*ta/2 + vi*(ti-ta-tb) + (mi1+vi)*tb/2
        lastspeed = mi1
    elif mi1 - first > ti:
        c = (first + first + ti)*ti/2
        lastspeed = first + ti
    else:
        a = (mi1+ti-first)/2
        c = (first+first+a)*a/2 + (first+a+mi1)*(ti-a)/2

        lastspeed = mi1


    return c, lastspeed


ans = 0
firstspeed = 0
for i in range(n):
    d,firstspeed = dist(firstspeed,i)

    ans += d

print(ans)

Solution (Python):

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

from itertools import accumulate as acm
T = [0] + list(acm(T))
V = V + [0]

nowSp = 0
dis = 0
nowTime = 0
from bisect import bisect_left as bl

while nowTime < T[-1]:
    nowTime += 0.5

    minV = min(T[i] - nowTime + V[i] for i in range(len(T)) if T[i] >= nowTime)    
    idx = bl(T, nowTime)-1
    minV=min(minV,V[idx])
    
    if minV > nowSp:
        minV = min(minV, nowSp + 0.5)
    if minV < nowSp:
        minV = min(minV, nowSp - 0.5)
    dis += (nowSp + minV) / 2 * 0.5
    nowSp = minV

print(dis)

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

time = sum(ts) + 1
speed_l = [0] * time
speed_r = [0] * time 

t_id = 0
speed = 0
ts_copy = ts[:]

for i in range(time+1):
    ts_copy[t_id] -= 1
    speed_l[i] = speed
    if speed >= vs[t_id]:
        speed = vs[t_id]
    else:
        speed += 0.5 

    if ts_copy[t_id] == 0:
        if t_id + 1 >= n:
            break
        t_id += 1


speed = 0
for i in range(time-1, -1, -1):
    ts[t_id] -= 1
    speed_r[i] = min(speed, speed_l[i])
    if speed >= vs[t_id]:
        speed = vs[t_id]
    else:
        speed += 0.5 

    if ts[t_id] == 0:
        if t_id <= 0:
            break
        t_id -= 1

print(sum(speed_r) / 2.0)

Solution (Python):
N=int(input())
now=0
T=list(map(int,input().split()))
for i in range(1,N):
    T[i]+=T[i-1]
T=[-1*float('inf'),0]+T+[float('inf')]
V=list(map(int,input().split()))
V=[0]+V+[0]
vt=[float('inf')]*(T[-2]+1)
for t in range(len(vt)):
    now=t
    for k in range(N+2):
        if now<T[k]:
            vt[t]=min(vt[t],V[k]+T[k]-now)
        elif T[k]<=now<=T[k+1]:
            vt[t]=min(vt[t],V[k])
        elif T[k+1]<now:
            vt[t]=min(vt[t],V[k]+now-T[k+1])
ans=0
for i in range(len(vt)-1):
    if abs(vt[i+1]-vt[i])==1:
        ans+=0.5*(vt[i]+vt[i+1])
    elif vt[i+1]==vt[i]:
        for k in range(N+2):
            if T[k]<=i and i+1<=T[k+1]:
                vv=V[k]
                break
        if vv>vt[i]:
            ans+=0.5*(vt[i]*2+0.5)
        else:
            ans+=vt[i]
print(ans)

Solution (Python):
def velsup(a,b,c,x):
    if a<=x<=b:
        return c
    elif x<a:
        return (a-x)+c
    else:
        return (x-b)+c

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+1)]
for i in range(N):
    S[i+1]=t[i]+S[i]
TT=S[N]
vt=[0 for i in range(2*TT+1)]
for tt in range(TT*2+1):
    ta=tt/2
    va=min(velsup(-1,0,0,ta),velsup(TT,TT+1,0,ta))
    for i in range(N):
        va=min(va,velsup(S[i],S[i+1],v[i],ta))
    vt[tt]=va
ans=0
for i in range(2*TT):
    ans+=(vt[i]+vt[i+1])*0.25
print(ans)

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

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]
lines.append((t,t+1,0))
def f(x):
    speed = 10**18
    for x1,x2,vv in lines:
        if x<x1:
            speed = min(speed,vv+x1-x)
        elif x>x2:
            speed = min(speed,vv+x-x2)
        else:
            speed = min(speed,vv)
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
res = sum(dp)*2-dp[0]-dp[-1]
print(res*0.25)

Solution (Python):
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
v.insert(0, 0)
v.append(0)
l = [0, 0]
r = [0]
for i in range(n):
    l.append(l[i+1]+t[i])
    r.append(l[i+2])
r.append(r[n])
d = 0
vl = 0
for k in range(l[n+1]*2):
    now = k / 2 + 0.5
    vr = 1000
    for i in range(n+2):
        tv = 0
        if now < l[i]:
            tv = v[i] + l[i] - now
        elif now < r[i]:
            tv = v[i]
        else:
            tv = v[i] + now - r[i]
        vr = min(vr, tv)
    d += (vl+vr) * 0.25
    vl = vr
print(d)

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

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

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