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


from itertools import accumulate

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

clock = [0] + list(accumulate(T))
t_sum = sum(T)
mn_f = 0
ans = 0
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        v = V[i-1]
        if t < clock[i-1]:
            v_max = v + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v_max = v
        else:
            v_max = v + t - clock[i]
        mn = min(mn, v_max)
    ans += (mn_f + mn) * 0.25
    mn_f = mn

ans += mn_f * 0.25

print(ans)

Solution (Python):
N = int(input())
tlist = list(map(int, input().split()))
vlist = list(map(int, input().split()))
vlist.append(0)
flag = True
while flag:
    flag =  False
    for i in range(N):
        if vlist[i]-vlist[i+1] > tlist[i]:
            vlist[i] = vlist[i+1]+tlist[i]
            flag = True
speed = 0
x = 0
for i in range(N):
    ti = tlist[i]
    vi = vlist[i]
    vj = vlist[i+1]
    if vi <= vj:
        if vi-speed <= ti:
            x += ti*vi - ((vi-speed)**2)/2
            speed = vi
        else:
            x += ti*(speed+ti) - (ti**2)/2
            speed += ti
    else:
        if speed+ti <= vj:
            x += ti*(speed+ti) - (ti**2)/2
            speed += ti
        elif 2*vi-speed-vj <= ti:
            x += ti*vi - ((vi-speed)**2)/2 - ((vi-vj)**2)/2
            speed = vj
        else:
            a = (ti+vj-speed)/2
            x += a*(2*speed+a)/2 + (ti-a)*(2*vj+ti-a)/2
            speed = vj
print(x)

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

Tsum = sum(T)
keika = []
tmp = 0
for i in range(N):
    keika.append([tmp,tmp+T[i]])
    tmp += T[i]

G = [[0]*(N+1) for i in range(2*Tsum+1)]

for i in range(2*Tsum+1):
    G[i][0] = min(i/2,Tsum-i/2)
for i in range(N):
    t0,t1 = keika[i]
    for j in range(2*t0):
        G[j][i+1] = V[i] + t0 - j/2
    for j in range(2*t0,2*t1+1):
        G[j][i+1] = V[i]
    for j in range(2*t1+1,2*Tsum+1):
        G[j][i+1] = V[i] + j/2 - t1

ans = 0
for i in range(2*Tsum):
    v0 = min(G[i])
    v1 = min(G[i+1])
    ans += (v0+v1)/4
print(ans)

Solution (Python):
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
T = [0]*(N+1)
for i in range(N):
    T[i+1] = T[i]+t[i]
def f(i, t):
    
    if T[i]<=t<=T[i+1]:
        return v[i]
    if t<T[i]:
        return v[i]+(T[i]-t)
    else:
        return v[i]+(t-T[i+1])
limit = [0]*(T[-1]*2+1)
for t in range(1, T[-1]*2+1):
    limit[t] = min(min(f(i, t/2) for i in range(N)), t/2, T[-1]-t/2)
print(sum(limit)/2)

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

tmax = sum(T)
Vmax = max(V)
dp = [[-1 * float('inf') for _ in range(Vmax + 1)] for _ in range(tmax)]
dp[0][0] = 0
i = 0
j = 0
vmax = V[0]
for t in range(1, tmax):
    i += 1
    if i == T[j] + 1:
        i = 1
        j += 1
        vmax = V[j]
    for v in range(1, vmax + 1):
        acc = dp[t - 1][v - 1] + v - 0.5 if v != 0 else 0.5
        if v < vmax:
            same = dp[t - 1][v] + v + 0.25
            bra = dp[t - 1][v + 1] + v + 0.5
        else:
            same = dp[t - 1][v] + v
            bra = -float('inf')
        dp[t][v] = max(acc, same, bra)

if tmax == 1:
    print(0.25)
else:
    print(dp[-1][1] + 0.5)

Solution (Python):

N = int(input())

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

alltime = sum(t)
maxslis = []
rmaxslis = []



spd = 0
ans = 0

for i in range(N):

    for j in range(t[i]):
        maxslis.append(v[i])
        maxslis.append(v[i])
        rmaxslis.append(v[i])


maxslis.reverse()


for i in range(alltime * 2):

    if i == 0:
        able = 0.5
        maxslis[i] = 0

    elif able < maxslis[i]:
        maxslis[i] = able
        able += 0.5

    else:
        able = maxslis[i]

maxslis.reverse()
maxslis.append(0)


dtflag = False

for i in range(alltime * 2 + 1):

    

    if spd < maxslis[i]:

        ans += spd * 0.5 + 0.125
        spd += 0.5
        
            

    elif spd == maxslis[i]:

        
            
            
        ans += spd * 0.5
        dtflag = False

    else:
        ans += spd * 0.5 - 0.125
        spd -= 0.5
        dtflag = False

print (ans)

Solution (Python):
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
T=[0,t[0]]
for i in range(n-1):
  T.append(T[i+1]+t[i+1])
L=[[] for i in range(2*sum(t))]
for i in range(2*sum(t)):
  for j in range(n):
    if T[j]<=i/2<=T[j+1]:
      x=v[j]
    elif i/2<T[j]:
      x=v[j]+abs(i/2-T[j])
    else:
      x=v[j]+abs(i/2-T[j+1])
    L[i].append(x)
for i in range(2*sum(t)):
  L[i].append(i/2)
  L[i].append(sum(t)-i/2)

for i in range(2*sum(t)):
  L[i]=min(L[i])
ans=0
for i in range(2*sum(t)):
  if i==2*sum(t)-1:
    ans+=L[i]*0.25
  else:
    ans+=(L[i]+L[i+1])*0.25
print(ans)

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

for i in range(1, N) :
        t[i] += t[i-1]
        
l = [t_ + v_ for t_, v_ in zip(t, v[1:]+[0])]
for i in range(N-2, -1, -1) :
    l[i] = min(l[i], l[i+1])
    
cur_v, cur_t = 0, 0
ret = 0
for i in range(N) :
    t1 = v[i] - cur_v + cur_t
    t2 = l[i] - v[i]
    if t[i] < t1 <= t2 :
        ret += (2 * cur_v + t[i] - cur_t) * (t[i] - cur_t) / 2
        cur_v = cur_v + t[i] - cur_t
        
    elif cur_t <= t1 <= t2 :
        ret += (t1 - cur_t) * (cur_v + v[i]) / 2
        if t2 <= t[i] :
            ret += (t2 - t1) * v[i]
            ret += (t[i] - t2) * (v[i] + l[i] - t[i]) / 2
            cur_v = l[i] - t[i]
        else :
            ret += (t[i] - t1) * v[i]
            cur_v = v[i]
    
    else :
        t3 = (l[i] + cur_t - cur_v) / 2
        if t3 >= t[i] :
            t3 = t[i]
        ret += (t3 - cur_t) * (2 * cur_v + t3 - cur_t) / 2
        ret += (t[i] - t3) * (2 * (cur_v + t3 - cur_t) - (t[i] - t3)) / 2
        if t3 == t[i] :
            cur_v = cur_v + t[i] - cur_t
        else :
            cur_v = l[i] - t[i]
    cur_t = t[i]
    
print(ret)

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

for i in range(n):
    l+=[v[i]]*t[i]*2

l=[min(i,j) for i,j in zip([0]+l,l+[0])]

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

ans=0

for i in range(1,len(l)):
    ans+=0.25*(l[i]+l[i-1])

print(ans)

Solution (Python):
f=lambda line,x:line[0]*x+line[1]
def _add_line(line,k,l,r):
    m=(l+r)//2
    if not data[k]:
        data[k]=line
        return
    lx,mx,rx=X[l],X[m],X[r-1]
    left,mid,right=f(line,lx)<f(data[k],lx),f(line,mx)<f(data[k],mx),f(line,rx)<f(data[k],rx)
    if left and right:
        data[k]=line
        return
    if not left and not right:return
    if mid:data[k],line=line,data[k]
    if left!=mid:_add_line(line,2*k+1,l,m)
    else:_add_line(line,2*k+2,m,r)
def add_line(line,a,b):
    L,R=a+N0,b+N0
    a0,b0=a,b
    sz=1
    while L<R:
        if R&1:
            R-=1
            b0-=sz
            _add_line(line,R-1,b0,b0+sz)
        if L&1:
            _add_line(line,L-1,a0,a0+sz)
            L+=1
            a0+=sz
        L>>=1
        R>>=1
        sz<<=1
def query(k):
    x=X[k]
    k+=N0-1
    s=10**18
    while k>=0:
        if data[k]:
            t=f(data[k],x)
            if t<s:s=t
        k=(k-1)//2
    return s
n,*t=map(int,open(0).read().split())
t,v=t[:n],t[n:]
st=sum(t)*2
m=a=i=0
N0=2**(st).bit_length()
data=[None]*(2*N0+1)
X=list(range(st+1))+[10**18]*N0
i=b=0
add_line((.5,0),0,st+1)
for u,w in zip(t,v):
    u+=u+i
    add_line((0,w),i,u)
    
    
    add_line((-.5,w+i/2),0,i+1)
    add_line((.5,w-u/2),u,st+1)
    i,b=u,w
add_line((-.5,st/2),0,st+1)
a=x=0
for i in range(1,st+1):
    y=query(i)
    a+=(x+y)/4
    x=y
print(a)

Solution (Python):
f=lambda line,x:line[0]*x+line[1]
def _add_line(line,k,l,r):
    m=(l+r)//2
    if not data[k]:
        data[k]=line
        return
    lx,mx,rx=X[l],X[m],X[r-1]
    left,mid,right=f(line,lx)<f(data[k],lx),f(line,mx)<f(data[k],mx),f(line,rx)<f(data[k],rx)
    if left and right:
        data[k]=line
        return
    if not left and not right:return
    if mid:data[k],line=line,data[k]
    if left!=mid:_add_line(line,2*k+1,l,m)
    else:_add_line(line,2*k+2,m,r)
def add_line(line,a,b):
    L,R=a+N0,b+N0
    a0,b0=a,b
    sz=1
    while L<R:
        if R&1:
            R-=1
            b0-=sz
            _add_line(line,R-1,b0,b0+sz)
        if L&1:
            _add_line(line,L-1,a0,a0+sz)
            L+=1
            a0+=sz
        L>>=1
        R>>=1
        sz<<=1
def query(k):
    x=X[k]
    k+=N0-1
    s=10**18
    while k>=0:
        if data[k]:
            t=f(data[k],x)
            if t<s:s=t
        k=(k-1)//2
    return s
n,*t=map(int,open(0).read().split())
t,v=t[:n],t[n:]
st=sum(t)*2
m=a=i=0
N0=2**(st).bit_length()
data=[None]*(2*N0+1)
X=list(range(st+1))+[10**18]*N0
i=b=0
add_line((.5,0),0,st+1)
for u,w in zip(t,v):
    u+=u+i
    add_line((0,w),i,u)
    add_line((-.5,w+i/2),0,i+1)
    add_line((.5,w-u/2),u,st+1)
    i,b=u,w
add_line((-.5,st/2),0,st+1)
a=x=0
for i in range(1,st+1):
    y=query(i)
    a+=(x+y)/4
    x=y
print(a)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    return


def B():
    return


def C():
    s = S()
    t = S()
    ansa = []
    anslis = []
    lisans = []
    for i in range(len(s)):
        for j in range(len(t)):
            if 0 <= i + j < len(s) and (s[i + j] == t[j] or s[i + j] == "?"):
                continue
            break
        else:
            ansa.append((i, i + j))
    if len(ansa) == 0:
        print("UNRESTORABLE")
        return
    for ans in ansa:
        a = ""
        for num in range(len(s)):
            i = s[num]
            if ans[0] <= num <= ans[1]:
                i = t[num-ans[0]]
            a += i
        anslis.append(a)
    for ans in anslis:
        k = ""
        for i in ans:
            if i == "?":
                k += "a"
            else:
                k += i
        lisans.append(k)
    lisans.sort()
    print(lisans[0])
        
    return











def D():
    n = II()
    t = LI()
    v = LI()
    t += [0]
    v = [0] + v + [0]
    time = [[0, 0]]
    for i in range(1, n+2):
        time.append((time[-1][1], time[-1][1] + t[i - 1]))
    def vx(x):
        res = inf
        for i in range(n+2):
            res = min(res, f(i, x))
        return res
    def f(i, x):
        l, r = time[i]
        vi = v[i]
        return vi + (l - x) if 0 <= x <= l else vi if l <= x <= r else vi + (x - r)
    ans = 0
    for x in range(sum(t) * 2):
        ans += 0.25 * (vx(x/2) + vx(x/2 + 0.5))
    print(ans)
    return


if __name__ == '__main__':
    D()

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

operations = T[:]
v_limits = V[:]

v = 0
limits_x = [0]
for i in range(N):
    for _ in range(operations[i]*2):
        v += 0.5
        limit = min(v, v_limits[i])
        limits_x.append(limit)
        v = limit
        
        
v = 0
limits_y = [0]
for i in reversed(range(N)):
    for _ in range(operations[i]*2):
        v += 0.5
        limit = min(v, v_limits[i])
        limits_y.append(limit)
        v = limit
limits_y = list(reversed(limits_y))



limits_z = [min(x,y) for x, y in zip(limits_x, limits_y)]


ans = 0
for _z, z in zip(limits_z[:-1],limits_z[1:]):
    ans += (_z+z)*0.5/2
print(ans)

Solution (Python):
from itertools import accumulate as ac
n=int(input())+2
t=[0]+list(map(int,input().split()))+[0]
v=[0]+list(map(int,input().split()))+[0]
s=[0]+list(ac(t))
def f(i,x):
    if s[i]<=x<=s[i+1]:return v[i]
    elif x<s[i]:return v[i]+s[i]-x
    else:return v[i]+x-s[i+1]
c=float("INF")
for i in range(n):
    c=min(c,f(i,0))
e=0
for i in range(1,2*s[-1]+1):
    i=i/2
    d=float("INF")
    for j in range(n):
        d=min(d,f(j,i))
    e+=0.25*(c+d)
    c=d
print(e)

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

t = [int(x) for x in input().split()]
vSection = [int(x) for x in input().split()]

vPoint = [0]
for i in range(1, N):
	vPoint.append(min(vSection[i - 1], vSection[i]))
vPoint.append(0)

for i in reversed(range(1, N + 1)):
	if t[i - 1] < vPoint[i - 1] - vPoint[i]:
		vPoint[i - 1] = t[i - 1] + vPoint[i]


ans = 0
VE = 0
for i in range(N):
	VS = VE
	if VS + t[i] <= vPoint[i + 1]:
		VE = VS + t[i]
		ans += VS * t[i] + t[i] ** 2 / 2
	else:
		VE = vPoint[i + 1]
		sumT = sum(t[:i])
		a = VS - (0 if i == 0 else sumT)
		b = VE + sum(t[:i+1])
		y = (a + b) / 2
		if y >= vSection[i]:
			t1 = vSection[i] - VS
			t2 = vSection[i] - VE
			ans += VS * t1 + t1 ** 2 / 2 + vSection[i] * (t[i] - t1 - t2) + VE * t2 + t2 ** 2 / 2
		else:
			x = y - a
			ans += VS * (x - sumT) + (x - sumT) ** 2 / 2 + VE * (t[i] - (x - sumT)) + (t[i] - (x - sumT)) ** 2 / 2
			
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N = int(input())
t, v = list(map(int, input().split())), list(map(int, input().split()))
s = sum(t)*2
u = [[0.5*i, 0.5*(s-i)] for i in range(s+1)]
T = [0] * (N+1)
for i in range(N):
    T[i+1] = T[i]+t[i]
for i in range(s):
    now = 0.5*i
    for j in range(N):
        if now < T[j]:
            u[i].append(v[j]+T[j]-now)
        elif T[j] <= now <= T[j+1]:
            u[i].append(v[j])
        else:
            u[i].append(v[j]+now-T[j+1])
for i in range(s+1):
    u[i] = min(u[i])
ans = 0
for i in range(s):
    ans += (u[i]+u[i+1])/4
print(ans)

Solution (Python):
from itertools import accumulate
import bisect


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

t = [0]+t
t = list(accumulate(t))

v.append(0)
for i in range(1,len(t)):
    v[-i-1] = min(v[-i]+t[-i]-t[-i-1],v[-i-1])


a = [0]

for i in range(1,(t[-1])*2+1):
    j = i/2
    b = bisect.bisect_left(t,j)
    a.append(min(a[-1]+1/2,v[b-1],v[b]+t[b]-j))
print(sum(a)/2)

Solution (Python):
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))+[0]
for i in range(n-1,-1,-1):
    v[i]=min(v[i],v[i+1]+t[i])
ans=0
v0=0
for i in range(n):
    if v[i]<=v[i+1]:
        if v[i]-v0>t[i]:
            ans+=(2*v0+t[i])*t[i]/2
            v0=v0+t[i]
        else:
            ans+=t[i]*v[i]-(v[i]-v0)**2/2
            v0=v[i]
    else:
        if v[i]*2-v0-v[i+1]<t[i]:
            ans+=t[i]*v[i]-(v[i]-v0)**2/2-(v[i]-v[i+1])**2/2
            v0=v[i+1]
        elif v[i+1]-v0>t[i]:
            ans+=(2*v0+t[i])*t[i]/2
            v0=v0+t[i]
        else:
            d=abs(v0-v[i+1])
            ans+=max(v0,v[i+1])*t[i]-d**2/2+(t[i]-d)**2/4
            v0=v[i+1]
print(ans)

Solution (Python):
N = int(input())
t = [int(Ti) for Ti in input().split()]
v = [int(Vi) for Vi in input().split()]

v_max = [0]
for ti, vi in zip(t, v):
    v_max[-1] = min(v_max[-1], vi)
    for _ in range(2*ti):
        v_max.append(vi)

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

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

area = 0
for i in range(len(v_max) - 1):
    area += 0.5 * 0.5 * (v_max[i] + v_max[i+1])

print(area)

Solution (Python):
from itertools import accumulate

N = int(input())
T = [int(s) for s in input().split()]
V = [int(s) for s in input().split()] + [0]
lt = sum(T)
S = list(accumulate(T))

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

vel2 = [0] * (2 * lt + 1)
for i in range(len(T)):
    ti = T[i]
    tr = S[i]
    for ts in range(tr - ti, tr):
        for t in (2 * ts + 1, 2 * ts + 2):
            if vel2[t-1] - (2 * tr - (t - 1)) == 2 * V[i+1]:
                vel2[t] = vel2[t-1] - 1
            elif vel2[t-1] == 2 * V[i]:
                vel2[t] = vel2[t-1]
            else:
                vel2[t] = vel2[t-1] + 1
ans = sum([(vel2[t-1] + vel2[t]) / 8 for t in range(1, 2 * lt + 1)])
print(ans)

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

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

INF = 1000
def main():
    Tmax = 0
    T = [0]
    for t in T0:
        Tmax += t
        T.append(Tmax)

    preh = 0
    ans = 0
    for t0 in range(2*Tmax+1):
        t = t0/2
        height = INF
        for n in range(-1, N+1):
            if n == -1:
                t1, t2, v = -1, 0, 0
            elif n == N:
                t1, t2, v = Tmax, Tmax+1, 0
            else:
                t1, t2, v = T[n], T[n+1], V[n]
            
            if t < t1:
                y = v + t1 - t
            elif t1 <= t <= t2:
                y = v
            else:
                y = v + t - t2
            height = min(height, y)
        
        ans += (preh + height)*0.5/2
        preh = height
    print(ans)

if __name__ == "__main__":
    main()

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

Tc = [0, 0] + [sum(T[:i + 1]) for i in range(N)] + [sum(T)]

ans = 0
for i in range(sum(T) * 2):
    t1, t2 = i * 0.5, (i + 1) * 0.5
    maxV1, maxV2 = [], []
    for j in range(N + 2):
        for t, maxV in [(t1, maxV1), (t2, maxV2)]:
            if t <= Tc[j]:
                maxV.append(V[j] + (Tc[j] - t))
            elif Tc[j] < t <= Tc[j + 1]:
                maxV.append(V[j])
            else:
                maxV.append(V[j] + (t - Tc[j + 1]))
    ans += 0.25 * (min(maxV1) + min(maxV2))

print(ans)

Solution (Python):



def ri():
    return int(input())

def rl():
    return list(input().split())

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

def mileage(t, v, vl, vr):
    assert(0 <= vl <= v and 0 <= vr <= v)
    
    l = v-vl
    r = t-(v-vr)
    if l > r:
        tmp = (l+r)/2
        l = tmp
        r = tmp
    ret = 0
    ret += l*l/2+vl*l
    ret += (r-l)*v
    ret += (t-r)*vr+(t-r)*(t-r)/2
    return ret

def main():
    n = ri()
    lt = rli()
    lv = rli()
    lt.append(0)
    lv.append(0)
    lefts = [0] 
    for i in range(n):
        left = min(lefts[i]+lt[i], lv[i], lv[i+1])
        offset = 0
        for j in range(i+1, n+1):
            left = min(left, offset+lv[j])
            offset += lt[j]
        lefts.append(left)
    
    ans = 0
    for i in range(n):
        ans += mileage(lt[i], lv[i], lefts[i], lefts[i+1])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
t = [0] + list(map(int, input().split()))
v = [0] + list(map(int, 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

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

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






        



N_INF = - 10 ** 15
DP = [[N_INF] * (102) for _ in range(100 * 200 + 2)] 
DP[0][0] = 0

time = 1
for i in range(N):
    
    
    for j in range(time, time + t[i]): 
        
        for k in range(0, v[i] + 1): 
            if k == 0: 
                
                
                DP[j][k] = max(DP[j - 1][0] + 0.25, DP[j - 1][1] + 1/2)
            elif k != v[i]: 
                DP[j][k] = max(DP[j - 1][k -1] + k - 1/2, DP[j - 1][k] + k + 0.25, DP[j - 1][k + 1] + k + 1/2)
            else: 
                DP[j][k] = max(DP[j - 1][k -1] + k - 1/2, DP[j - 1][k] + k)
        
    time += t[i]

print (DP[time - 1][0])

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

st = sum(t)
maxv = [0]
for i in range(n):
    maxv[-1] = min(maxv[-1],v[i])
    for _ in range(2*t[i]):
        maxv.append(v[i])
maxv[-1] = 0
for i in range(1,2*st+1):
    maxv[i] = min(maxv[i],maxv[i-1] + 0.5)
for i in range(2*st)[::-1]:
    maxv[i] = min(maxv[i],maxv[i+1] + 0.5)
ans = 0
for i in range(2*st):
    ans += (maxv[i] + maxv[i+1])*0.5 / 2
print(ans)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def main():
    N = i_inpl()
    t = l_inpl()
    v = l_inpl()

    T = sum(t)
    max_v = [0]

    for i in range(N):
        max_v[-1] = min(v[i], max_v[-1])
        max_v.extend([v[i]]*t[i]*2)

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

    max_v[-1] = 0
    for i in range(2*T-1, 0, -1):
        max_v[i] = min(max_v[i+1]+0.5, max_v[i])
    
    
    
    ans = 0
    for i in range(2*T-1):
        ans += max_v[i] * 0.5 + (max_v[i+1]-max_v[i]) * 0.5
    
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
inpt=list(map(int,input().split()))
inpv=list(map(int,input().split()))

t=inpt+[0]
v=inpv+[0]

T=sum(t)
M=[0]

nowt=2*t[0]
nowmaxv=v[0]
nowv=M[0]
i=0

for time in range(2*T):
    if nowv+0.5<=v[i]:
        M.append(nowv+0.5)
    else:
        M.append(nowv)
    nowt-=1
    nowv=M[-1]
    if nowt==0:
        i+=1
        nowt=2*t[i]
        nowmaxv=v[i]
        nowv=min(nowv,nowmaxv)
        
t=list(reversed(inpt))+[0]
v=list(reversed(inpv))+[0]
m=[0]

nowt=2*t[0]
nowmaxv=v[0]
nowv=M[0]
i=0

for time in range(2*T):
    if nowv+0.5<=v[i]:
        m.append(nowv+0.5)
    else:
        m.append(nowv)
    nowt-=1
    nowv=m[-1]
    if nowt==0:
        i+=1
        nowt=2*t[i]
        nowmaxv=v[i]
        nowv=min(nowv,nowmaxv)

ans=[min(M[i],m[-i-1]) for i in range(len(M))]
print(sum([min(ans[i],ans[i+1])+(ans[i+1]-ans[i])**2 for i in range(len(ans)-1)])/2)

Solution (Python):
N = int(input())
*T, = map(int, input().split())
*V, = map(int, input().split())
speed = [0] 
for t, v in zip(T, V):
    speed[-1] = min(speed[-1], v)
    speed += [v]*(2*t)
speed[-1] = 0
temp = 0
for t in range(1, len(speed)):
    speed[t] = temp =  min(speed[t], temp + 0.5)
temp = 0
for t in range(len(speed)-1, 0, -1):
    speed[t] = temp =  min(speed[t], temp + 0.5)
ans = sum((v1 + v2)/4 for v1, v2 in zip(speed, speed[1:]))
print(ans)

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

ans = 0
for i in range(1,N+1):
    T[i] += T[i-1]
time = T[-1]
upper  = {}

state = N
speed = 0

for t in range(2*time,0,-1):
    t *= 0.5
    if T[state-1] == t:
        speed = min(V[state],speed)
        state -= 1
    upper[t] = min(speed,V[state])
    speed += 0.5

speed = 0
pre = -1
Ans = []
for t in range(1,2*time+1):
    t = t*0.5
    speed += 0.5
    speed = min(speed,upper[t])
    Ans.append(speed)
    if pre == speed:
        ans += 0.5*speed
    elif pre > speed:
        ans += 0.5*speed + 0.125
    else:
        ans += 0.5*speed - 0.125
    pre = speed
print(ans)

Solution (Python):
def f(v,t,now):
    res = now
    s = 0
    for i in range(len(t)-1):
        s+=t[i]
        if s-t[i]>=now:
            res = min(res,v[i]+s-t[i]-now)
        elif s>=now>=s-t[i]:
            res = min(res,v[i])
        else:
            res = min(res,v[i]+now-s)
    res = min(res, s-now)
    return max(res,0)
n = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
t.append(0)
v.append(0)
ans = []
for i in range(sum(t)+1):
    ans.append(f(v,t,i))
    ans.append(f(v, t, i+0.5))
r = 0
for i in range(len(ans)-1):
    r+=(ans[i]+ans[i+1])/4
print(r)

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)
    MAX_V.extend([v] * (2 * t))

REAL_V = [0]
for i in range(len(MAX_V) - 1):
    REAL_V.append(min(REAL_V[-1] + 0.5, MAX_V[i + 1]))

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

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

Solution (Python):
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
need=[(0,0)]*(N+1)
now=0
for i in range(N-1):
    now+=T[i]
    need[i+1]=(now,min(V[i],V[i+1]))
need[N]=(now+T[N-1],0)
TN=need[N][0]
res=[float('inf')]*(TN+1)
for i in range(TN+1):
    for j in range(N+1):
        if j>0:
            if need[j-1][0]<=i<=need[j][0]:
                res[i]=min(res[i],V[j-1])
        res[i]=min(res[i],need[j][1]+abs(need[j][0]-i))
ans=0
for i in range(TN):
    if abs(res[i]-res[i+1])==1:
        ans+=0.5*(res[i]+res[i+1])
    else:
        for j in range(N):
            if need[j][0]<=i and i+1<=need[j+1][0]:
                vv=V[j]
                break
        if vv>res[i]:
            ans+=res[i]+0.25
        else:
            ans+=res[i]
print(ans)

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

L=[0]
for i in range(N):
    a=[v[i] for j in range(t[i]*2)]
    
    L+=a
X=[]
for i in range(1,len(L)):
    if L[i-1]>L[i]:
        X.append(i)
for i in X:
    L[i-1]=L[i]
L[-1]=0

S=copy.deepcopy(L)


for i in range(1,len(L)):
    if L[i-1]<L[i]:
        for j in range(10**5):
            if S[i-1]+0.5*j>400 or (i-1+j)>(len(L)-1):
                break
            else:
                S[i-1+j]=min(S[i-1]+0.5*j,S[i-1+j])
    elif L[i-1]>L[i]:
        for j in range(10**5):
            if S[i]+0.5*j>400 or i<j:
                break
            else:
                S[i-j]=min(S[i]+0.5*j,S[i-j])

ans=0
for i in range(1,len(S)):
    ans+=(S[i-1]+S[i])/2
print(ans/2)