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):
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    T = [t * 2 for t in T]
    V = [v * 2 for v in V]
    Tall = sum(T)
    R = [0] * (Tall + 1)
    j = N - 1
    tc, vc, vn = T[-1], V[-1], V[-1]
    R[-1] = 0
    for i in reversed(range(Tall)):
        tc -= 1
        if tc == 0:
            j -= 1
            tc, vn = T[j], V[j]
        R[i] = min(R[i + 1] + 1, vc, vn)
        vc = vn
    v = 0
    d = 0.0
    j = 0
    tc, vc, vn = T[j], V[j], V[j]
    T.append(0)
    V.append(0)
    for i in range(1, Tall + 1):
        tc -= 1
        if tc == 0:
            j += 1
            tc, vn = T[j], V[j]
        vnn = min(v + 1, R[i], vc, vn)
        d += (v + vnn) / 2
        vc = vn
        v = vnn
    print(d / 4)

main()

Solution (Python):





def solve(T, V, velocity):
    accT = 1
    for t, max_v in zip(T, V):
        for i in range(accT, accT+2*t):
            velocity[i] = min(velocity[i], velocity[i-1]+0.5, max_v)
        accT += 2*t


def main():

    N, *A = map(int, open(0).read().split())
    T = A[:N]
    V = A[N:]

    INF = 10**10

    velocity = [INF]*(sum(T)*2+1)
    velocity[0] = 0
    velocity[-1] = 0
    solve(T, V, velocity)
    velocity = velocity[::-1]
    solve(T[::-1], V[::-1], velocity)

    ans = 0
    pre_v = velocity[0]
    for v in velocity[1:]:
        ans += (pre_v + v) * 0.25
        pre_v = v

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

left = [0] * (N + 1)
right = [0] * (N + 1)

for i in range(1, N):
    start = left[i - 1]
    left[i] = min(start + T[i], V[i], V[i + 1])

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

total = [min(left[i], right[i]) for i in range(N + 1)]
ans = 0
for i in range(1, N + 1):
    x = (V[i] - total[i - 1]) + (V[i] - total[i])
    if x >= T[i]:
        V[i] = (total[i - 1] + T[i] + total[i]) / 2
        x = T[i]
    d =(total[i - 1] + V[i]) * (V[i] - total[i - 1]) / 2 
    d += (total[i] + V[i]) * (V[i] - total[i]) / 2 
    d += V[i] * (T[i] - x) 

    ans += d

print (ans)

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

vel_go=[0]
for ti, v_lim in zip(T,V):
    for _ in range(ti*2):
        v = min(vel_go[-1] + 0.5, v_lim)
        vel_go.append(v)

vel_back = [0]
for ti, v_lim in zip(T[::-1], V[::-1]):
    for _ in range(ti*2):
        v = min(vel_back[-1] + 0.5, v_lim)
        vel_back.append(v)
vel_back.reverse()

velocity = tuple(min(x,y) for x, y in zip(vel_go, vel_back))
ans = sum(0.25*(x+y) for x,y in zip(velocity[:-1], velocity[1:]))
print(ans)

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

vel_go = [0]
for ti, v_lim in zip(T, V):
    for _ in range(ti * 2):
        v = min(vel_go[-1] + 0.5, v_lim)
        vel_go.append(v)

vel_back = [0]
for ti, v_lim in zip(T[::-1], V[::-1]):
    for _ in range(ti * 2):
        v = min(vel_back[-1] + 0.5, v_lim)
        vel_back.append(v)
vel_back.reverse()

velocity = tuple(min(x, y) for x, y in zip(vel_go, vel_back))
ans = sum(0.25*(x+y) for x, y in zip(velocity[:-1], velocity[1:]))
print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

def dist(i, j, lim, t):
	if abs(i - j) > t:
		dist = -INF
	else:
		x = (t + j - i) / 2
		y = (t + j + i) / 2
		if  y <= lim:
			dist = (i + y) * x / 2 + (j + y) * (t - x) / 2
		else:
			dist = (i + lim) * (lim - i) / 2 + lim * (t - (lim - i) - (lim - j)) + (j + lim) * (lim - j) / 2
			

	return dist


def main():
	N = int(input())
	T = getlist()
	V = getlist()
	DP = [[-INF] * 101 for i in range(N + 1)]
	DP[0][0] = 0
	for i in range(N - 1):
		lim = V[i]
		t = T[i]
		for p in range(lim + 1):
			for q in range(lim + 1):
				d = dist(p, q, lim, t)
				DP[i + 1][q] = max(DP[i + 1][q], DP[i][p] + d)

	lim = V[-1]
	t = T[-1]
	for p in range(lim + 1):
		d = dist(p, 0, lim, t)
		DP[N][0] = max(DP[N][0], DP[N - 1][p] + d)


	print(DP[N][0])

if __name__ == '__main__':
	main()

Solution (Python):
INF = 10**18

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
V = [0] + V + [0]
R = [(0, 0)]*(N+2)
for i in range(1,N+1):
    R[i] = (R[i-1][1], R[i-1][1] + T[i-1])
R[N+1] = (R[N][1], R[N][1])
def velocity(i, x):
    if x < R[i][0]:
        return V[i]+R[i][0]-x
    elif R[i][0] <= x <= R[i][1]:
        return V[i]
    else:
        return V[i]+x-R[i][1]
ans = 0
dp = [0]*(R[N+1][1]*2+1)
for x in range(1, R[N+1][1]*2+1):
    mi = INF
    for i in range(N+2):
        mi = min(velocity(i, x/2), mi)
    dp[x] = mi
    ans += 0.25*(dp[x-1]+mi)
print(ans)

Solution (Python):
def calc(left, right, time, vmax):
    if left <= time and time <= right:
        return vmax
    elif time < left:
        return vmax + left - time
    else:
        return vmax + time - right

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

tmax = sum(t)
vnow = 0
ans = 0
for i in range(1, 2*tmax+1):
    time = 0.5 * i
    vmin = 10**9
    for j in range(n):
        left, right = tlst[j][0], tlst[j][1]
        vmax = v[j]
        vmin = min(vmin, calc(left, right, time, vmax))
    vmin = min(vmin, calc(0, 0, time, 0))
    vmin = min(vmin, calc(tmax, tmax, time, 0))
    ans += 0.25 * (vmin + vnow)
    vnow = vmin
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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):
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
end = [-1]*N
end[-1] = 0

for i in range(N-2, -1, -1):
    end[i] = min(end[i+1]+t[i+1], v[i], v[i+1])

ans = 0
s = 0

for i in range(N):
    e = end[i]

    if s+t[i]<=e:
        ans += (s+s+t[i])*t[i]/2
        s = s+t[i]
    else:
        up = min(v[i], (s+e+t[i])/2)
        ans += (s+up)*(up-s)/2
        ans += (e+up)*(up-e)/2
        ans += up*(t[i]-(up-s)-(up-e))
        s = e

print(ans)

Solution (Python):
n = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))
s = [0]*n
for i in range(n-1):
    s[i+1] = s[i] + T[i]
l = (s[-1]+T[n-1])*2+1
ans = [1e100]*l

for i in range(l):
    ans[i] = min(ans[i],i/2)
    ans[l-i-1] = min(ans[i],i/2)

for j in range(n):
    for i in range(l):
        if i <= s[j]*2:
            ans[i] = min(ans[i], V[j]+(s[j]*2-i)/2)
        elif s[j]*2 <= i <= s[j]*2+T[j]*2:
            ans[i] = min(ans[i],V[j])
        else:
            ans[i] = min(ans[i],V[j]+(i-s[j]*2-T[j]*2)/2)
anser = 0
for i in range(l-1):
    anser += (ans[i]+ans[i+1])/4
print(anser)

Solution (Python):
n=int(input())
t=list(map(int,input().split()))
u=list(map(int,input().split()))
speed=[0]
for i in range(n):
  speed+=[u[i]]*t[i]*2
speed.append(0)
m=len(speed)
for i in range(1,m):
  speed[i-1]=min(speed[i-1],speed[i])
del speed[-1]
m-=1
for i in range(1,m):
  speed[i]=min(speed[i],speed[i-1]+0.5)
for i in range(m-2,-1,-1):
  speed[i]=min(speed[i],speed[i+1]+0.5)
ans=0
for i in range(1,m):
  ans+=abs(speed[i-1]+speed[i])*0.25
print(ans)

Solution (Python):
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
M = 2
dt = 1 / M
R = sum(T)

maxSpeeds = [10**18] * (R * M + 1)
now = 0
for t, v in zip(T, V):
    for i in range(t * M + 1):
        maxSpeeds[now + i] = min(maxSpeeds[now + i], v)
    now += t * M

maxSpeeds[0] = 0
maxSpeeds[-1] = 0
for t in range(1, R * M + 1):
    maxSpeeds[t] = min(maxSpeeds[t - 1] + dt, maxSpeeds[t])
    maxSpeeds[-(t + 1)] = min(maxSpeeds[-t] + dt, maxSpeeds[-(t + 1)])

ans = 0
for l, r in zip(maxSpeeds, maxSpeeds[1:]):
    ans += (l + r) / M / 2
print(ans)

Solution (Python):
N = int(input())
T = [int(a) * 2 for a in input().split()]
V = [int(a) * 2 for a in input().split()]
MA = [0] * (sum(T) + 1)
a = 0
for i in range(N):
    for j in range(T[i]):
        a += 1
        MA[a] = min(MA[a-1] + 1, V[i])
MA[a] = 0
for i in range(N)[::-1]:
    for j in range(T[i]):
        a -= 1
        MA[a] = min(MA[a], MA[a+1] + 1, V[i])

print((sum(MA[1:]) + sum(MA[:-1])) / 8)

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

l = sum(T) * 2 + 1
t_cond = [0] + T + [0]
v_cond = [0] + V + [0]
memo = [[0] * l for _ in range(N + 2)]
left = 0
for i in range(N + 2):
    for j in range(l):
        if j < left:
            memo[i][j] = v_cond[i] + (left - j) * 0.5
        elif left <= j <= left + t_cond[i] * 2:
            memo[i][j] = v_cond[i]
        else:
            memo[i][j] = v_cond[i] + (j - left - t_cond[i] * 2) * 0.5
            
    
    left += t_cond[i] * 2

f = [min(memo[i][j] for i in range(N + 2)) for j in range(l)]
ans = 0
for i in range(l - 1):
    ans += 0.25 * (f[i] + f[i + 1])
print(ans)

Solution (Python):
N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))


answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)

Solution (Python):
def calc_vt(v,t):
    vt = [0]*(sum(t)*2+1)
    t_sum = 0
    for ti,vi in zip(t,v):
        for i in range(ti*2):
            vt[t_sum + 1 + i] = min(vt[t_sum + i] + 0.5,vi)
        t_sum += ti*2
    return vt

n = input().split()
tn = list(map(int,input().split()))
vn = list(map(int,input().split()))

vt_l = calc_vt(vn,tn)
vt_r = calc_vt(vn[::-1],tn[::-1])[::-1]

vt_lr = [min(vl,vr) for vl,vr in zip(vt_l,vt_r)]

print(sum((a+b)*0.5/2 for a,b in zip(vt_lr,vt_lr[1:])))

Solution (Python):
import sys
from collections import *
import heapq
import math

import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

t.append(0)
v.append(0)
t.insert(0,0)
v.insert(0,0)

tt=sum(t)
lst=[0]*(tt*2+1)

for i in range(tt*2-1):
    tmp=[]
    now=0.5+i/2
    cnt=0
    for j in range(n+2):
        l=cnt
        cnt+=t[j]
        r=cnt
        if j==n+1:
            l=r
        if now<=l:
            tmp.append(l-now+v[j])
        elif r<=now:
            tmp.append(now-r+v[j])
        else:
            tmp.append(v[j])
        
    lst[i+1]=min(tmp)


ans=0
for i in range(tt*2):
    ans+=0.25*(lst[i+1]+lst[i])
print(ans)

Solution (Python):


import io
import math
import scipy.sparse
import numpy

data = int(input())

array1 = list(map(lambda x:int(x)*2,input().split()))

array2 = list(map(lambda x:int(x)*2,input().split()))

sumt = sum(array1)

maxv = [min(i, sumt-i) for i in range(sumt+1)]

counter = 0

for t,v in zip(array1,array2):
    for i in range(counter,counter+t+1):
        maxv[i] = min(maxv[i], v)
    counter += t

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

print(sum(maxv) / 4)

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

dp = [[-1]*102 for _ in range(sum(T) + 1)]
dp[0][0] = 0

nt = 0
pt = T[0]

delta = [-1,0,1]
for i in range(sum(T)):
    if pt == i:
        nt += 1
        pt += T[nt]
    for j in range(101):
        if j > V[nt] or dp[i][j] == -1:break
        for d in delta:
            nj = j + d
            if 0 <= nj <= V[nt]:
                if d != 0 or j == V[nt]:
                    dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + (j+nj)/2)
                else :
                    dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + j + 0.25)

print(dp[-1][0])

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))






N = I()
t = LI()
v = [0] + LI() + [0]

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

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

A = [0]*(N+1)
for i in range(N+1):
    A[i] = min(L[i],R[i])

ans = 0
for i in range(1,N+1):
    if A[i-1] >= A[i]:
        x = (t[i-1]-A[i-1]+A[i])/2
        if A[i-1]+x <= v[i]:
            ans += (A[i-1]+x/2) * x \
                     + (A[i-1]+x+A[i])/2 * (x+A[i-1]-A[i])
        else:
            ans += (A[i-1]+v[i])/2 * (v[i]-A[i-1]) \
                     + v[i] * (t[i-1]-2*v[i]+A[i-1]+A[i]) \
                     + (v[i]+A[i])/2 * (v[i]-A[i])
    else:
        x = (t[i-1]-A[i]+A[i-1])/2
        if A[i]+x <= v[i]:
            ans += (A[i]+x/2) * x \
                     + (A[i]+x+A[i-1])/2 * (x+A[i]-A[i-1])
        else:
            ans += (A[i-1]+v[i])/2 * (v[i]-A[i-1]) \
                     + v[i] * (t[i-1]-2*v[i]+A[i-1]+A[i]) \
                     + (v[i]+A[i])/2 * (v[i]-A[i])

print(ans)

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

N = int(input())
t = list(accumulate([0] + list(map(int, input().split())) + [0]))
v = [0] + list(map(int, input().split())) + [0]
prev = 0
ans = 0
T = t[-1]
for i in range(0, 2*T+1):
    i /= 2
    cur = i
    for j in range(N+1):
        l = t[j]
        r = t[j+1]
        u = v[j+1]
        if i < l:
            cur = min(cur, u + (l - i))
        elif i > r:
            cur = min(cur, u + (i - r))
        else:
            cur = min(cur, u)
    ans += (prev + cur) / 4
    prev = cur
print(ans)

Solution (Python):
n = int(input())
trng = [0]+list(map(int,input().split()))+[0]
vlim = [0]+list(map(int,input().split()))+[0]
n += 2
smt = sum(trng)
table = [[-1 for i in range(smt*2+1)] for j in range(n)]
acc = 0
for i in range(n):
  if i == 0:
    for j in range(smt*2+1):
      table[i][j] = j/2
  elif i == n-1:
    for j in range(smt*2+1):
      table[i][j] = smt-table[0][j]
  else:
    v = vlim[i]
    t = trng[i]
    for j in range(acc):
      table[i][j] = v+(acc-j)/2
    for j in range(acc,acc+t*2+1):
      table[i][j] = v
    acc += t*2
    for j in range(acc+1,smt*2+1):
      table[i][j] = v+(j-acc)/2
ans = 0
ansls = list(zip(*table))
for arr in ansls:
  ans += min(arr)*0.5
print(ans)

Solution (Python):
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
runtime = sum(t)
speed = [0] * (runtime*2+1)
now_t, now_v = 0,0
for ti,vi in zip(t,v):
  for i in range(now_t*2+1,now_t*2+ti*2+1):
    next_v = min(now_v+0.5, vi)
    speed[i] = next_v
    now_v = next_v
  now_t += ti
speed[-1] = 0
now_t, now_v = runtime,0
for ti,vi in zip(t[::-1],v[::-1]):
  for i in range(now_t*2-1,now_t*2-ti*2-1,-1):
    next_v = min([now_v+0.5, speed[i],vi])
    speed[i] = next_v
    now_v = next_v
  now_t -= ti
ans = 0
for i in range(runtime*2):
  ans += speed[i]+speed[i+1]
ans /= 4
print(ans)

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

unit = 2

acumT = [0] * (n + 1)
for i in range(n):
  acumT[i+1] = acumT[i] + T[i+1]
  
PV = [0] * (sum(T) * unit + 1)
for p in range(1, n + 1):
  t1 = acumT[p-1]
  t2 = acumT[p]

  for i in range(t1 * unit, t2 * unit + 1):
    ii = i / unit 
    PV[i] = min([ii - acumT[k] + V[k] for k in range(0, p)] + [V[p]] + [-ii + acumT[m] + V[m+1] for m in range(p, n+1)])

area = sum((i + j) / unit / 2 for i, j in zip(PV, PV[1:]))  
print(area)

Solution (Python):
n=int(input())
t=[int(a)*2 for a in input().split()]
v=[int(a)*2 for a in input().split()]
ma=[0]*(sum(t)+1)
a=0
for i in range(n):
  for j in range(t[i]):
    a+=1
    ma[a]=min(ma[a-1]+1,v[i])
ma[a]=0
for i in range(n)[::-1]:
  for j in range(t[i]):
    a-=1
    ma[a]=min(ma[a],ma[a+1]+1,v[i])
print((sum(ma[1:])+sum(ma[:-1]))/8)

Solution (Python):
n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      if a>100:
        break
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)

Solution (Python):
n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)

Solution (Python):
n = int(input())
t = list(map(int, input().split())) + [0]
v = list(map(int, input().split())) + [0]
m = sum(t)*2
g = [10**10]*(m+1)
l = [(0, 0, 0)]
for x, y in zip(t, v):
  l.append((l[-1][1], l[-1][1] + x*2, y))
for x, y, c in l:
  for i in range(m + 1):
    d = c
    if i < x:
      d += (x - i)*.5
    elif y < i:
      d += (i - y)*.5
    if g[i] > d:
      g[i] = d
print(sum(g)/2)

Solution (Python):
N = int(input())
T = list(map(lambda t: int(t) * 10, input().split()))
V = list(map(int, input().split())) + [0]
R = sum(T)

maxSpeed = [10**18] * (R + 1)
maxSpeed[0] = 0
maxSpeed[R] = 0
now = 0
for i, t in enumerate(T):
    now += t
    maxSpeed[now] = min(V[i], V[i + 1])

now = 0
for v, t in zip(V, T):
    for i in range(t + 1):
        maxSpeed[now + i] = min(maxSpeed[now + i], v)
    now += t

for t in range(1, R + 1):
    maxSpeed[t] = min(maxSpeed[t], maxSpeed[t - 1] + 0.1)
for t in range(R)[::-1]:
    maxSpeed[t] = min(maxSpeed[t], maxSpeed[t + 1] + 0.1)

base = 0
upper = 0
for v1, v2 in zip(maxSpeed, maxSpeed[1:]):
    base += min(v1, v2)
    upper += abs(v1 - v2)
ans = base + upper / 2
print(ans / 10)

Solution (Python):

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

Ts = sum(T)


Vmax = [float("inf")] * (Ts * 2 + 1)

ts = 0
for i in range(N):
    for t in range(T[i]):
        t1 = (ts + t) * 2
        t2 = (ts + t) * 2 + 1
        Vmax[t1] = min(Vmax[t1], V[i])
        Vmax[t2] = min(Vmax[t2], V[i])

    
    Vmax[(ts + T[i]) * 2] = min(Vmax[(ts + T[i]) * 2], V[i])

    ts += T[i]


Vmax[0] = Vmax[Ts * 2] = 0

for t in range(Ts * 2):
    Vmax[t + 1] = min(Vmax[t + 1], Vmax[t] + 0.5)

for t in range(Ts * 2 - 1, 0, -1):
    Vmax[t] = min(Vmax[t], Vmax[t + 1] + 0.5)

ans = 0.0
for i in range(Ts * 2):
    
    ans += (Vmax[i] + Vmax[i + 1]) * 0.5 / 2

print(ans)

Solution (Python):
N = int(input())
T = list(map(int, input().split()))
V1 = list(map(int, input().split()))
V1.append(0)

ST = [0] * (N + 1)
for i in range(N):
    ST[i + 1] = ST[i] + T[i]

V2 = [0] * N
for i in range(N):
    V2[i] = V1[i + 1] + ST[i + 1]
z = V2[-1]
for i in range(N - 1, -1, -1):
    if V2[i] > z:
        V2[i] = z
    else:
        z = V2[i]


Vmax = [0] * (ST[-1] * 2 + 1)
j = 0
t = 0
for i, Tn in enumerate(ST):
    while t < Tn or j == 0:
        Vmax[2 * t + j] = min(V1[i - 1], V2[i - 1])
        V2 = [x - 0.5 for x in V2]
        t += j
        j ^= 1

v, cnt = 0, 0
for i in range(ST[-1] * 2):
    nVmax = Vmax[i + 1]
    nv = min(v + 0.5, nVmax)
    cnt += (v + nv) * 0.5 / 2
    v = nv

print(cnt)

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

speed = [10 ** 9] * (2 * time + 1)
limit = [10 ** 9] * (2 * time + 1)

i = 0
for j, k in zip(t, v):
    for _ in range(j * 2):
        limit[i] = min(limit[i], k)
        i += 1
    limit[i] = min(limit[i], k)

s = 0
for i in range(2 * time + 1):
    s = min(s, limit[i])
    speed[i] = min(speed[i], s)
    s += 0.5
s = 0
for i in reversed(range(2 * time + 1)):
    s = min(s, limit[i])
    speed[i] = min(speed[i], s)
    s += 0.5

dist = 0
for i in range(2 * time):
    dist += (speed[i] + speed[i + 1]) / 4
print(dist)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, t: "List[int]", v: "List[int]"):
    bounds = [[] for _ in range(N)]
    gb0 = (1, 0)
    tend = sum(t)
    gb1 = (-1, tend)
    for i in range(N):
        bounds[i].append(gb0)
        bounds[i].append(gb1)
    stt = 0
    for i in range(N):
        ti = t[i]
        vi = v[i]
        end = stt + ti
        b0 = (-1, stt + vi)
        b1 = (0, vi)
        b2 = (1, -end + vi)
        for j in range(i):
            bounds[j].append(b0)
        bounds[i].append(b1)
        for j in range(i + 1, N):
            bounds[j].append(b2)
        stt = end
    stt = 0
    vms = [0] * (tend * 2 + 1)
    for i in range(N):
        end = stt + t[i]
        bi = bounds[i]
        inf = float("inf")
        mins = {-1: inf, 0: inf, 1: inf}
        for a, b in bi:
            mins[a] = min(mins[a], b)
        for tm in range(stt * 2, end * 2):
            vms[tm] = min(a * tm + b * 2 for a, b in mins.items())
        stt = end
    print(sum(vms) / 4)


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 heapq
n=int(input())
inf=10000000000000
ans=[[-1,-1] for i in range(n)]
ans[-1][1],ans[0][0]=0,0
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v2=[]
for i in range(n):
    heapq.heappush(v2,(v[i],i))

def next(y,wh):
    global ans,n
    ansi=inf
    if wh:
        r1,r2=range(y[1]-1,-1,-1),range(y[1],n)
    else:
        r1,r2=range(y[1],-1,-1),range(y[1]+1,n)
    now=0
    for j in r1:
        if ans[j][1]!=-1:
            ansi=min(ansi,ans[j][1]+now)
        now+=t[j]
        if ans[j][0]!=-1:
            ansi=min(ansi,ans[j][0]+now)
    now=0
    for j in r2:
        if ans[j][0]!=-1:
            ansi=min(ansi,ans[j][0]+now)
        now+=t[j]
        if ans[j][1]!=-1:
            ansi=min(ansi,ans[j][1]+now)  
    if wh:
        ans[y[1]][0]=min(ansi,y[0])
        ans[y[1]-1][1]=ans[y[1]][0]
    else:
        ans[y[1]][1]=min(ansi,y[0])
        ans[y[1]+1][0]=ans[y[1]][1]  

for i in range(n):
    y=heapq.heappop(v2)
    if ans[y[1]][0]==-1:next(y,True)
    if ans[y[1]][1]==-1:next(y,False)
answer=0
for i in range(n):
    h=min((t[i]+sum(ans[i]))/2,v[i])
    answer+=((h**2-ans[i][0]**2)/2)
    answer+=((h**2-ans[i][1]**2)/2)
    answer+=(h*(t[i]+sum(ans[i])-2*h))
print(answer)

Solution (Python):
import heapq
n=int(input())
inf=10000000000000


ans=[[-1,-1] for i in range(n)]
ans[-1][1]=0
ans[0][0]=0
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v2=[]
for i in range(n):
    heapq.heappush(v2,(v[i],i))
for i in range(n):
    
    y=heapq.heappop(v2)
    
    
    
    
    if ans[y[1]][0]==-1:
        
        now1=0
        ansi1=inf
        for j in range(y[1]-1,-1,-1):
            
            if ans[j][1]!=-1:
                ansi1=min(ansi1,ans[j][1]+now1)
            now1+=t[j]
            if ans[j][0]!=-1:
                ansi1=min(ansi1,ans[j][0]+now1)
        now1=0
        for j in range(y[1],n):
            if ans[j][0]!=-1:
                ansi1=min(ansi1,ans[j][0]+now1)
            now1+=t[j]
            if ans[j][1]!=-1:
                ansi1=min(ansi1,ans[j][1]+now1)  
        ans[y[1]][0]=min(ansi1,y[0])
        ans[y[1]-1][1]=ans[y[1]][0]
        
    if ans[y[1]][1]==-1:
        
        now2=0
        ansi2=inf
        for j in range(y[1],-1,-1):
            if ans[j][1]!=-1:
                ansi2=min(ansi2,ans[j][1]+now2)
            now2+=t[j]
            if ans[j][0]!=-1:
                ansi2=min(ansi2,ans[j][0]+now2)
        now2=0
        for j in range(y[1]+1,n):
            if ans[j][0]!=-1:
                ansi2=min(ansi2,ans[j][0]+now2)
            now2+=t[j]
            if ans[j][1]!=-1:
                ansi2=min(ansi2,ans[j][1]+now2)  
        ans[y[1]][1]=min(ansi2,y[0])
        ans[y[1]+1][0]=ans[y[1]][1]
        
answer=0
for i in range(n):
    h=min((t[i]+sum(ans[i]))/2,v[i])
    answer+=((h**2-ans[i][0]**2)/2)
    answer+=((h**2-ans[i][1]**2)/2)
    answer+=(h*(t[i]+sum(ans[i])-2*h))
print(answer)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    T=LI()
    V=LI()
    T_sum = sum(T)

    
    max_V = [inf]*(2*T_sum+1)
    now = 0
    for i,(t,v) in enumerate(zip(T,V)):
        max_V[now] = min(max_V[now], v)
        for dt in range(2*t):
            now += 1
            max_V[now] = min(max_V[now], v)
    max_V[0] = 0
    max_V[-1] = 0


    
    for i in range(2*T_sum):
        max_V[i+1] = min(max_V[i+1], max_V[i]+0.5)

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

    
    ans = 0
    for i in range(2*T_sum):
        ans += (max_V[i]+max_V[i+1])/2

    ans /= 2
    print(ans)
            

if __name__ == '__main__':
    main()