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().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
vtmax=[0]
tmp=0
Tsum=sum(T)
for t,v in zip(T,V):
    vtmax[-1]=min(tmp,v) 
    vtmax+=[v]*(t*2)
    tmp=v
vtmax[-1]=0

for i in range(1,2*Tsum):
    vtmax[i]=min(vtmax[i],vtmax[i-1]+0.5)
for i in range(2*Tsum-1,0,-1):
    vtmax[i]=min(vtmax[i],vtmax[i+1]+0.5)
area=0
for i,vt in enumerate(vtmax):
    if i==0:continue
    area+=0.5*(vt+vtmax[i-1])/2
print(area)

Solution (Python):
def atcoder_express(N: int, T: list, V: list)->float:
    MAXT = sum(T)
    graph = [0] * (2*MAXT + 1)

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

    V = [0] + V + [0]

    conditions = []
    for i in range(N+2):
        v, l, r = V[i], T[i], T[i+1]
        conditions.append((l, r, v))

    total = 0.0
    prev_v = 0.0
    for t in range(MAXT*2+1):
        min_v = float('inf')
        x = t / 2
        for l, r, v in conditions:
            if x < l:
                min_v = min(min_v, v + (l - x))
            elif r < x:
                min_v = min(min_v, v + (x - r))
            else:
                min_v = min(min_v, v)
        total += (prev_v + min_v) * 0.5 / 2
        prev_v = min_v

    return total


if __name__ == "__main__":
    N = int(input())
    T = [int(s) for s in input().split()]
    V = [int(s) for s in input().split()]
    ans = atcoder_express(N, T, V)
    print(ans)

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

    ans = editorial(N, t, v)
    print(ans)
    
    
    
    
    

    
    
    
    


def editorial(N, ts, vs):
    maxv = []
    for v, t in zip(vs, ts):
        maxv.extend([v] * 2 * t)

    
    
    
    
    
    
    
    
    
    
    maxv = [0] + [min(v1, v2) for v1, v2 in zip(maxv, maxv[1:])]
    maxv.append(0)

    max_t = len(maxv)
    bef_v = 0
    for i in range(max_t):
        bef_v = maxv[i] = min(maxv[i], bef_v + 0.5)
    aft_v = -0.5
    for i in range(max_t)[::-1]:
        aft_v = maxv[i] = min(maxv[i], aft_v + 0.5)

    ans = 0
    for v1, v2 in zip(maxv, maxv[1:]):
        ans += (v1 + v2) * 0.5 / 2

    return ans


def fix_maxv(maxv, max_t):
    """
    0123456789 -> t
      2--23--3 -> v

      のように見えるけど実際は違う

    """
    maxv = maxv[:]
    tmp = [None] * 3
    tmp[0] = maxv[:]
    bef_v = 0
    for i in range(max_t):
        bef_v = maxv[i] = min(maxv[i], bef_v + 0.5)

    
    tmp[1] = maxv[:]
    aft_v = -0.5
    for i in range(max_t)[::-1]:
        aft_v = maxv[i] = min(maxv[i], aft_v + 0.5)
    tmp[2] = maxv[:]
    for i in range(max_t):
        print(*([0.5 + i/2] + [tmp[j][i] for j in range(3)]), sep="\t")

    return maxv


def editorial_WA(N, ts, vs):
    
    maxv = []
    for v, t in zip(vs, ts):
        maxv.extend([v] * 2 * t)
    default_maxv = [v + 0.05 for v in maxv]

    max_t = sum(ts) * 2
    maxv = fix_maxv(maxv, max_t)

    import os
    
    
    
    
    local = "Darwin" in str(os.uname())
    if local:
        import matplotlib
        
        matplotlib.use("TkAgg")
        import matplotlib.pyplot as plt
        real_ts = [i / 2 for i in range(1, len(maxv) + 1)]
        plt.plot(real_ts, maxv, color="red")
        plt.plot(real_ts, default_maxv, color="blue")
        plt.show()
        
        

    ans = 0
    
    
    
    for t, (v1, v2) in enumerate(zip([0] + maxv, maxv), 1):
        
        trapezoid = (v1 + v2) * 0.5 / 2
        ans += trapezoid
        if local:
            print(t / 2, v1, v2, trapezoid, ans, sep="\t")

    return ans


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N = int(input())
    T = list(map(int, input().split()))
    V_limit = list(map(int, input().split()))

    V = []
    for i in range(N):
        V += [V_limit[i] for _ in range(2 * T[i])]

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

    V = [0] + V
    V[-1] = 0

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

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

    ans = 0
    for i in range(len(V)-1):
        ans += 0.25 * (V[i] + V[i+1])
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
time = list(map(int, input().split()))
speed = list(map(int, input().split()))
speed = [0] + speed + [0]
cumtime = [0] * (n+1)
for i in range(n):
    cumtime[i+1] = cumtime[i] + time[i]
dis = 0.0
prev = 0
l = cumtime[n]
tp = 1
for t in range(1, l+1):
    if t > cumtime[tp]:
        tp += 1
    v = speed[tp]
    v = min(v, prev + 1)
    for i in range(tp):
        v = min(v, t - cumtime[i] + speed[i])
    for i in range(tp+1, n+2):
        v = min(v, cumtime[i-1] - t + speed[i])
    if v == prev and v < speed[tp]:
        dis += v + 1/4
    else:
        dis += (v + prev) / 2
    prev = v
print(dis)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    r,g = IR(2)
    print(2*g-r)


def B():
    n = I()
    k = I()
    a = 1
    for i in range(n):
        if a > k:
            a += k
        else:
            a *= 2
    print(a)

def C():
    def check(a,b):
        for i in range(len(a)):
            if a[i] != b[i] and a[i] != "?":
                return False
        return True
    def f(c):
        if c == "?":return "a"
        return c
    s = S()
    t = S()
    n = len(s)
    l = len(t)
    ans = []
    for i in range(n-l+1)[::-1]:
        if check(s[i:i+l],t):
            c = [f(s[j]) for j in range(i)]
            c += t
            for j in range(i+l,n):
                c += f(s[j])
            ans.append(c)
    if not len(ans):
        print("UNRESTORABLE")
    else:
        ans.sort()
        for i in ans[0]:
            print(i,end = "")
        print()

def D():
    n = I()
    t = LI()
    v = LI()
    v.append(0)
    for i in range(n-1):
        t[i+1] += t[i]
    vt = defaultdict(int)
    k = 0
    for i in range(t[-1]*2+1):
        nt = i/2
        if nt >= t[k]:
            k += 1
        vt[nt] = v[k]
    for i in range(n)[::-1]:
        for j in range(t[i]*2+1)[::-1]:
            nt = j/2
            if -nt+v[i+1]+t[i] < vt[nt]:
                vt[nt] = -nt+v[i+1]+t[i]
    ans = 0
    nv = 0
    for i in range(1,t[-1]*2+1):
        nt = i/2
        if nv < vt[nt-0.5]:
            ans += 0.125+nv/2
            nv += 0.5
        elif nv == vt[nt]:
            ans += nv/2
        else:
            if nv > vt[nt]:
                nv -= 0.5
                ans += 0.125+nv/2
            else:
                ans += nv/2
    print(ans)

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):
from itertools import chain
  
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
  
va = list(chain.from_iterable([v] * (2 * t) for t, v in zip(ts, vs)))
va = [min(v1, v2) for v1, v2 in zip([0] + va, va + [0])]
lt = len(va)
  
pv = 0
for ct in range(1, lt):
    va[ct] = pv = min(va[ct], pv + 0.5)
  
pv = 0
for ct in range(lt - 1, 0, -1):
    va[ct] = pv = min(va[ct], pv + 0.5)
  
print(sum((v1 + v2) / 4 for v1, v2 in zip(va, va[1:])))

Solution (Python):
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    C = [0] * (N+1)
    for i in range(N-1):
        C[i+1] = min(V[i], V[i+1])
    for _ in range(N):
        for i in range(N):
            left = C[i]
            right = C[i+1]
            C[i] = min(C[i], right + T[i])
            C[i+1] = min(C[i+1], left + T[i])
    ans = 0
    for i in range(N):
        if (V[i] - C[i]) + (V[i] - C[i+1]) < T[i]:
            lx = V[i] - C[i]
            rx = V[i] - C[i+1]
            ans += (C[i] + V[i]) * lx / 2 + \
                (C[i+1] + V[i]) * rx / 2 + \
                V[i] * (T[i]-lx-rx)
        else:
            M = max(C[i], C[i+1])
            m = min(C[i], C[i+1])
            x = (T[i] - (M-m)) / 2
            ans += (M + M+x) * x / 2 + (m + M+x) * (x+(M-m)) / 2
    print(ans)


if __name__ == "__main__":
    main()

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

b = 2
bg = 1.0 / b

M = [] 
for i in range(n) :
    for j in range(T[i] * b) :
        M.append(V[i])

R = [0] + T[:]
for i in range(n) :
    R[i+1] += R[i]


for i in range(n) :

    le = R[i] * b
    ri = R[i+1] * b

    
    j = 0
    if i-1 >= 0 and V[i-1] > V[i] :
        while le >= 0 :
            M[le] = min(M[le], V[i] + j*bg)
            
            j += 1
            le -= 1
    j = 0
    if i+1 < n and V[i+1] > V[i] :
        while ri < len(M) :
            M[ri] = min(M[ri], V[i] + j*bg)
            j += 1
            ri += 1

for i in range(len(M)) :
    M[i] = min(i*bg, (len(M)-i)*bg, M[i])

M += [0]

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

print(ans)

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

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


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

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

Solution (Python):
import numpy as np
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T = [0, 0] + T + [0]
V = [0] + V + [0]
accT = np.cumsum(T)
INF = 10 ** 9

t2_max = accT[-1] * 2
speeds = np.ones(t2_max + 1) * INF
for t0, t1, v in zip(accT[:-1], accT[1:], V):
    sptmp = np.ones(t2_max + 1) * v
    sptmp[:t0 * 2] += np.arange(t0, 0, -0.5)
    sptmp[t1 * 2:] += np.arange(0, accT[-1] - t1 + 0.5, 0.5)
    speeds = np.minimum(speeds, sptmp)

ans = sum(speeds) / 2

print(ans)

Solution (Python):

N = int(input()) 
T = list(map(lambda x: int(x)*2, input().split()))
V = list(map(lambda x: int(x)*2, input().split())) + [0]

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

ct = 0
for t,v in zip(T,V):
    for i in range(ct, ct+t+1):
        maxv[i] = min(maxv[i], v)
    ct += 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(float( sum(maxv) ) / 4)

Solution (Python):

def calc_area(v_end, v_start, v_max, dt):
    kouten_v = (v_end + v_start + dt) / 2
    kouten_t = kouten_v - v_start
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2 
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2 
        area -=  max(0, (kouten_v - v_max))** 2 
    else:
        area = (v_start + v_end) *  dt / 2
    return area

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

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

    
    for i in range(n-1):
        if  max_velocity[-(i+1)] - max_velocity[-(i+2)] < -t[-(i+1)]:
            max_velocity[-(i+2)] = max_velocity[-(i+1)] + t[-(i+1)]

    
    ans = 0
    for i in range(n):
        ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
    print(ans)

main()

Solution (Python):

def calc_area(v_end, v_start, v_max, dt):
    kouten_v = (v_end + v_start + dt) / 2
    kouten_t = kouten_v - v_start
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2 
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2 
        area -=  max(0, (kouten_v - v_max))** 2 
    else:
        area = (v_start + v_end) *  dt / 2
    return area

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

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

    
    for i in range(n-1):
        if  max_velocity[-(i+1)] - max_velocity[-(i+2)] < -t[-(i+1)]:
            max_velocity[-(i+2)] = max_velocity[-(i+1)] + t[-(i+1)]

    
    ans = 0
    for i in range(n):
        ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
    print(ans)

main()

Solution (Python):
def calc_area(v_end, v_start, v_max, dt):
    kouten_v = (v_end + v_start + dt) / 2
    kouten_t = kouten_v - v_start
    kouten_t_limit1 = max(v_max - v_start, 0)
    kouten_t_limit2 = min(v_end + dt - v_max, dt)
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2
        area -=  (kouten_t_limit2  - kouten_t_limit1) * max(0, (kouten_v - v_max)) / 2
    else:
        area = (v_start + v_end) *  dt / 2
    return area

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

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

ok = 0
while ok==0:
    for i in range(n-1):
        if  abs((max_velocity[i+1]-max_velocity[i])/t[i]) >1:
                max_velocity[i]=max_velocity[i]-1
                break
    else:
        ok=1



ans = 0
for i in range(n):
    ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
print(ans)

Solution (Python):
N = int(input())
t = [0] + list(map(int, input().split())) + [0]
v = [0] + list(map(int, input().split())) + [0]
for i in range(N, 0, -1):
    v[i] = min(v[i], v[i + 1] + t[i])
for i in range(1, N + 1):
    v[i] = min(v[i], v[i - 1] + t[i])
ans = 0
v_f = 0
for i in range(1, N + 1):
    v_l = min(v_f + t[i], v[i + 1], v[i])
    if 2 * v[i] - v_f - v_l <= t[i]:
        ans += (v[i] + v_f) * (v[i] - v_f) / 2 + v[i] * (t[i] - 2 * v[i] + v_f + v_l) + (v[i] + v_l) * (v[i] - v_l) / 2
    else:
        t_1 = (t[i] + v_l - v_f) / 2
        t_2 = t[i] - t_1
        ans += (2 * v_f + t_1) * t_1 / 2 + (2 * v_l + t_2) * t_2 / 2
    v_f = v_l
print('{:.10f}'.format(ans))

Solution (Python):
n = int(input())
t = [int(m) for m in input().split()]
T = sum(t)
v = [int(m) for m in input().split()]
v.append(0)

maxv=[0]

i = 0
cnt = 0

while i < n:
    cnt += 0.5
    if t[i] == cnt:
        maxv.append(min(v[i],v[i+1]))
        i += 1
        cnt = 0
    else:
        maxv.append(v[i])
maxv[0] = 0

maxv[2*T] = 0

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

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

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

print(ans)

Solution (Python):
N = int(input())
t_list = list(map(int, input().split()))
v_list = list(map(int, input().split()))
t_sum = sum(t_list)
v_max = [0.0] * (2 * t_sum + 1)

t_i = 0
v_i = 0
t = t_list[t_i]
v = v_list[v_i]
time = 0
for i in range(1, 2 * t_sum + 1):
    time += 0.5
    if time >= t:
        time = 0
        t_i += 1
        v_i += 1
        if t_i >= N:
            break
        t = t_list[t_i]
        v_max[i] = min(min(v, v_list[v_i]), v_max[i - 1] + 0.5)
        v = v_list[v_i]
        continue
    v_max[i] = min(v, v_max[i - 1] + 0.5)

t_i = N - 1
v_i = N - 1
t = t_list[t_i]
v = v_list[v_i]
v_max[-1] = 0
time = 0
for i in range(2 * t_sum - 1, -1, -1):
    time += 0.5
    if time >= t:
        t_i -= 1
        v_i -= 1
        if t_i < 0:
            break
        t = t_list[t_i]
        v = v_list[v_i]
        time = 0
    if v_max[i] > v_max[i + 1] + 0.5:
        v_max[i] = v_max[i + 1] + 0.5

ans = 0
for i in range(len(v_max)-1):
    ans += (v_max[i] + v_max[i+1]) * 0.25
print(ans)

Solution (Python):
INF = 10 ** 20
n = int(input())
tlst = list(map(int, input().split()))
vlst = list(map(int, input().split()))
dp = [[-INF] * 201 for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    t, v = tlst[i], vlst[i]
    for v_fr in range(v + 1):
        pre_score = dp[i][v_fr]
        for v_to in range(v + 1):
            diff = abs(v_to - v_fr)
            if diff > t:continue
            max_speed = min((v_to + v_fr + t) / 2, v)
            dp[i + 1][v_to] = max(dp[i + 1][v_to], pre_score + max_speed * t - (max_speed - v_to) ** 2 / 2 - (max_speed - v_fr) ** 2 / 2)
print(dp[n][0])

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

dp = [[-float('inf')]*(101) for _ in range(N+1)]
V.append(0)

dp[0][0] = 1

for i in range(N):
    for v in range(V[i]+1):
        for vv in range(V[i]+1):
            past_dist = dp[i][v]
            if 2*V[i]-v-vv <= T[i]:
                a = V[i]-v
                b = V[i]-vv
                c = (v+V[i])*a/2 + V[i]*(T[i] - a - b) + (vv+V[i])*b/2
                dp[i+1][vv] = max(dp[i+1][vv], c+past_dist)
            elif T[i] >= abs(vv-v):
                ta = (vv-v+T[i])/2
                tb = (T[i]+v-vv)/2
                c = (2*v+ta)*ta/2 + (vv+v+ta)*tb/2
                dp[i+1][vv] = max(dp[i+1][vv], c+past_dist)

print(dp[N][0]-1)

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

dp = [[-float('inf')]*(101) for _ in range(N+1)]
V.append(0)

dp[0][0] = 1

for i in range(N):
    for v in range(V[i]+1):
        for vv in range(V[i]+1):
            past_dist = dp[i][v]
            if 2*V[i]-v-vv <= T[i]:
                a = V[i]-v
                b = V[i]-vv
                c = (v+V[i])*a/2 + V[i]*(T[i] - a - b) + (vv+V[i])*b/2
                dp[i+1][vv] = max(dp[i+1][vv], c+past_dist)
            elif T[i] >= abs(vv-v):
                ta = (vv-v+T[i])/2
                tb = (T[i]+v-vv)/2
                c = (2*v+ta)*ta/2 + (vv+v+ta)*tb/2
                dp[i+1][vv] = max(dp[i+1][vv], c+past_dist)

print(dp[N][0]-1)

Solution (Python):
from itertools import accumulate
N = int(input())
t = [0]*2 + list(map(int, input().split())) + [0]
v = [0] + list(map(int, input().split())) + [0]
N += 3

at = list(accumulate(t))
T = at[-1]

s = [0]*(2*T+1)

minvs = []
for i in range(2*T+1):
    t = i*0.5
    minv = 10**10
    for j in range(N-1):
        if t < at[j]:
            tmpv = v[j] + (at[j]-t)
        elif at[j] <= t and t <= at[j+1]:
            tmpv = v[j]
        else:
            tmpv = v[j] + (t-at[j+1])
        minv = min(minv, tmpv)
    minvs.append(minv)
ans = 0.0
for i in range(2*T):
    ans += (minvs[i]+minvs[i+1])*0.25
print(ans)

Solution (Python):
"""
def func(n, t, v):
    t = [0] + t + [t[-1]]
    print("t:{}".format(t))
    v = [0] + v + [0]

    limit = [0 for _ in range(t[-1] + 1)]
    for i in reversed(range(len(t) - 1)):
        for j in range(t[i] - t[i-1]):
            limit[t[i] - j] = min(v[i + 1] + j, v[i])

    print(limit)
    print([[i, limit[i]] for i in range(len(limit))])
    
    dist = 0
    prev = 0
    for i in range(1, len(limit)):
        next = min(prev + 1, limit[i])
        dist += (next + prev) / 2
        print("i:{} add:{} dist:{}".format(i, (next + prev) / 2, dist))
        prev = next
    return str(dist)
"""
def func(n, t, v):
    t = [0] + t + [t[-1]]
    v = [0] + v + [0]
    for i in range(len(t)):
        t[i] *= 2
    for i in range(len(v)):
        v[i] *= 2
    

    limit = [0 for _ in range(t[-1] + 1)]
    for i in reversed(range(len(t) - 1)):
        for j in range(t[i] - t[i-1]+1):
            limit[t[i] - j] = min(limit[t[i]] + j, v[i])

    
    
    
    dist = 0
    prev = 0
    for i in range(1, len(limit)):
        next = min(prev + 1, limit[i])
        dist += (next + prev) / 2
        
        prev = next
    return str(dist/4)


n = int(input())
t = [int(i) for i in input().split()]
for i in range(1, len(t)):
    t[i] += t[i-1]
v = [int(i) for i in input().split()]
print(func(n, t, v))

"""
print("2100 vs " + func(1, [100], [30]) + "\n")
print("2632 vs " + func(2, [60, 110], [34, 38]) + "\n")
print("76 vs " + func(3, [12, 26, 28], [6, 2, 7]) + "\n")
print("20.25 vs " + func(1, [9], [10]) + "\n")
print(
    "20291 vs " + func(10, [64, 119, 146, 181, 257, 376, 383, 401, 450, 550], [29, 19, 31, 39, 27, 48, 41, 87, 55, 70]))
"""

Solution (Python):


"""
参考：http://ferin-tech.hatenablog.com/entry/2017/10/28/231616
・愚直に3重ループでシミュレーション
"""

N = int(input())
tN = list(map(int, input().split()))
vN = list(map(int, input().split()))

tN.append(0)
vN.append(0)

dist = 0
speed = 0
for i in range(N):
    keep = True
    plus = True
    
    for j in [0.5*x for x in range(tN[i]*2)]:
        
        if speed == vN[i]:
            plus = False
        rest = tN[i] - j
        
        for k in range(i+1, N+1):
            if vN[k] < vN[i] and rest <= speed - vN[k]:
                keep = False
                plus = False
            rest += tN[k]
        
        if plus:
            
            dist += speed/2
            speed += 0.5
            dist += 0.125
        elif keep:
            dist += speed/2
        else:
            speed -= 0.5
            dist += speed/2
            dist += 0.125
print(dist)

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 i in range(2 * t):
        maxv.append(v)

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

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

ans = 0
for i in range(T - 1):
    ans += (maxv[i] + maxv[i + 1]) * 0.5 / 2

print(ans)

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

MAX_V = [0]

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


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

MAX_V[-1] = 0

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

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

print(ans)

Solution (Python):
N = int(input())
T = [int(_) for _ in input().split()]
for i in range(N - 1):
    T[i + 1] += T[i]
T = [0] + T
V = [int(_) for _ in input().split()]
V = V
vel = [min(i / 2, T[-1] - i / 2) for i in range(2 * T[-1] + 1)]
for i in range(N):
    for j in range(2 * T[-1] + 1):
        vel[j] = min(vel[j],
                     max(V[i], -j / 2 + T[i] + V[i], j / 2 - T[i + 1] + V[i]))
print((2 * sum(vel) - vel[0] - vel[-1]) / 4)

Solution (Python):

from pprint import pprint
N = int(input())
tn = list(map(int, input().split()))
vn = list(map(int, input().split()))

tn_sum = sum(tn)
time_tbl = [0 for _ in range(tn_sum*2+1)]  

lrv = []
lrv.append([0, 0, 0])
t_sum = 0
for t, v in zip(tn, vn):
    lrv.append([t_sum, t_sum+t, v])
    t_sum += t
lrv.append([tn_sum, tn_sum, 0])


def f(l,r,x,v):
    if x <= l:
        return v + l - x
    elif l < x < r:
        return v
    else:
        return v + x - r

for t05 in range(tn_sum*2+1):
    time_tbl[t05] = min([f(l, r, t05/2, v) for l, r, v in lrv])

area = .0
for i in range(tn_sum*2):
    area += (time_tbl[i] + time_tbl[i+1])/4

print(area)

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

T_p = [0,0]
temp = 0
for tt in T:
    temp += tt
    T_p.append(temp)
T_p.append(temp)

Tmax = temp

def vv(i,tt):
    a = T_p[i]
    b = T_p[i + 1]
    if i == 0 or i == N + 1:
        vmax = 0
    else:
        vmax = V[i - 1]
    
    if tt >= b:
        res = tt - b + vmax
    elif tt <= a:
        res = a - tt + vmax
    else:
        res = vmax

    return res

mints = [min([vv(i, tt/2) for i in range(N + 2)]) for tt in range(2 * Tmax + 1)]

res = 0
for i in range(len(mints) -1 ):
    res += (mints[i] + mints[i + 1])/4

print(res)

Solution (Python):
N = int( input())
T = list( map( int, input().split())) + [0]
V = list( map( int, input().split())) + [0]
now = 0
end = min( V[0], now + T[0])
ans = 0
for i in range(N):
    
    t = T[i]
    v = V[i]
    end = min( v, now + t)
    plus = 0
    for j in range(i, N):
        end = min( end, V[j+1]+plus)
        plus += T[j+1]
    x, y = (end + t - now)/2, (end + t + now)/2
    
    if y <= v:
        
        
        ans += (now+y)*x/2 + (end+y)*(t-x)/2
        
    else:
        
        
        ans += (v+now)*(v-now)/2 + (v+end)*(v-end)/2+v*(end-2*v+t+now)
        
    now = end
print(ans)

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

import itertools
tv = [0] + list(itertools.chain(*[[v] * t * 2 for t, v in zip(T, V)])) + [0]
for i in itertools.accumulate(T):
    tv[i * 2] = min(tv[i * 2], tv[i * 2 + 1])
for i in range(len(tv)-1, 0, -1):
    if tv[i] < tv[i-1] - 0.5:
        tv[i-1] = tv[i] + 0.5
    elif tv[i] > tv[i-1] + 0.5:
        for j in range(i, len(tv) - 1):
            if tv[j-1] + 0.5 < tv[j]:
                tv[j] = tv[j-1] + 0.5
            else:
                break
print(sum([(v1 + v2) * 0.5 * 0.5 for v1, v2 in zip(tv[1:], tv[:-1])]))

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

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

ct = 0
for t,v in zip(T,V):
    for i in range(ct,ct+t+1):
        maxv[i] = min(maxv[i], v)
    ct += 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):
v = 0
t = 0
n = int(input())
T = [0] + list(map(int, input().split())) + [0]
V = [0] + list(map(int, input().split())) + [0]
cumT = [0] * (len(T) + 1)
for i in range(len(T)):
    cumT[i + 1] = cumT[i] + T[i]
imos = [1000] * (sum(T) + 1)

for i in range(len(T)):
    for j in range(T[i]):
        imos[cumT[i] + j] = V[i]
horizon = imos.copy()
for i in range(len(T)):
    for j in range(len(imos) - cumT[i + 1]):
        imos[cumT[i + 1] + j] = min([imos[cumT[i + 1] + j], V[i] + j])
    for j in range(cumT[i + 1]):
        imos[cumT[i] - j] = min([imos[cumT[i] - j], V[i] + j])

ret = 0.0
for i in range(len(imos) - 1):
    ret += (imos[i] + imos[i + 1] + 0.5 if imos[i] == imos[i + 1] and imos[i] < horizon[i] else imos[i] + imos[i + 1]) / 2
print(ret)

Solution (Python):
N = int(input())
T = [int(i) for i in input().split()]
L = [0]
for i in range(N):
    L.append(L[i] + T[i])
V = [int(i) for i in input().split()]

def VM(x, i): 
    if 0 <= x <= L[i]:
        return V[i] + (L[i] - x)
    elif L[i] < x <= L[i+1]:
        return V[i]
    else:
        return V[i] + (x - L[i+1])

Search = [[] for i in range(N)] 
for i in range(N):
    for j in range(N):
        if i < j and V[i] - V[j] > L[j] - L[i+1]:
            Search[i].append(j)
        elif i > j and V[i] - V[j] > L[i] - L[j+1]:
            Search[i].append(j)

maxV = [float("inf") for i in range(2*L[-1]+1)]
for i in range(N):
    for j in range(2 * L[i], 2 * L[i+1] + 1):
        maxV[j] = min(V[i], j * 0.5, L[-1] - j * 0.5) 
        for s in Search[i]:
            maxV[j] = min(maxV[j], VM(j * 0.5, s))
Ans = 0
for i in range(2*L[-1]):
    Ans += (maxV[i] + maxV[i+1])/4
print(Ans)