Problem:
 ﻿Score : 400 points    Problem Statement In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express .  In the plan developed by the president Takahashi, the trains will run as follows:   A train will run for (t_1 + t_2 + t_3 + ... + t_N) seconds.  In the first t_1 seconds, a train must run at a speed of at most v_1 m/s (meters per second). Similarly, in the subsequent t_2 seconds, a train must run at a speed of at most v_2 m/s, and so on.   According to the specifications of the trains, the acceleration of a train must be always within ±1m/s^2 . Additionally, a train must stop at the beginning and the end of the run.  Find the maximum possible distance that a train can cover in the run.      Constraints  1 \leq N \leq 100  1 \leq t_i \leq 200  1 \leq v_i \leq 100  All input values are integers.         Input Input is given from Standard Input in the following format:  N  t_1  t_2  t_3 … t_N  v_1  v_2  v_3 … v_N       Output Print the maximum possible that a train can cover in the run. Output is considered correct if its absolute difference from the judge's output is at most 10^{-3} .        Sample Input 1 1
100
30      Sample Output 1 2100.000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 30 seconds, it accelerates at a rate of 1m/s^2 , covering 450 meters.  In the subsequent 40 seconds, it maintains the velocity of 30m/s , covering 1200 meters.  In the last 30 seconds, it decelerates at the acceleration of -1m/s^2 , covering 450 meters.   The total distance covered is 450 + 1200 + 450 = 2100 meters.       Sample Input 2 2
60 50
34 38      Sample Output 2 2632.000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 34 seconds, it accelerates at a rate of 1m/s^2 , covering 578 meters.  In the subsequent 26 seconds, it maintains the velocity of 34m/s , covering 884 meters.  In the subsequent 4 seconds, it accelerates at a rate of 1m/s^2 , covering 144 meters.  In the subsequent 8 seconds, it maintains the velocity of 38m/s , covering 304 meters.  In the last 38 seconds, it decelerates at the acceleration of -1m/s^2 , covering 722 meters.   The total distance covered is 578 + 884 + 144 + 304 + 722 = 2632 meters.       Sample Input 3 3
12 14 2
6 2 7      Sample Output 3 76.000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 6 seconds, it accelerates at a rate of 1m/s^2 , covering 18 meters.  In the subsequent 2 seconds, it maintains the velocity of 6m/s , covering 12 meters.  In the subsequent 4 seconds, it decelerates at the acceleration of -1m/s^2 , covering 16 meters.  In the subsequent 14 seconds, it maintains the velocity of 2m/s , covering 28 meters.  In the last 2 seconds, it decelerates at the acceleration of -1m/s^2 , covering 2 meters.   The total distance covered is 18 + 12 + 16 + 28 + 2 = 76 meters.       Sample Input 4 1
9
10      Sample Output 4 20.250000000000000000   The maximum distance is achieved when a train runs as follows:   In the first 4.5 seconds, it accelerates at a rate of 1m/s^2 , covering 10.125 meters.  In the last 4.5 seconds, it decelerates at the acceleration of -1m/s^2 , covering 10.125 meters.   The total distance covered is 10.125 + 10.125 = 20.25 meters.       Sample Input 5 10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70      Sample Output 5 20291.000000000000

Solution (Python):
N=int(input())
t_List=[int(i) for i in input().split()]
t_Table=[0]
for i in range(N):
  t_Table.append(t_Table[i]+t_List[i])
v_List=[int(i) for i in input().split()]
v_List.append(0)
Class=0
t=0
v=0
L=0
check=0
while t<=t_Table[-1]:
  for i in range(Class+1,N+1):
    if t_Table[i]!=t:
      if (v_List[i]-v)/(t_Table[i]-t)==-1:
        L+=v/2-1/8
        v+=-0.5
        check=-1
        break
  if check!=-1: 
    if v==v_List[Class]:
      L+=v/2
    else:
      L+=v/2+1/8
      v+=0.5
  t+=0.5
  if t_Table[Class+1]==t and Class<=N-2:
    Class+=1
    check=0
print(L)

Solution (Python):
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T0 = sum(T)
INF = float("inf")
M = 2 * T0 + 1
l, r = 0, 0
maxv = [INF] * M
for i in range(N):
    l = r
    r += T[i]
    for k in range(2 * l, 2 * r + 1):
        maxv[k] = min(maxv[k], V[i])

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

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


ans = 0
for i in range(1, M):
    ans += 0.25 * (maxv[i] + maxv[i - 1])

print(ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
t = reads()
v = reads()
psumt = [0] + list(accumulate(t))
T = psumt[-1]

vs = [0] * (T+1)
ans = 0
for ss in range(0, 2 * T):
  s = ss / 2
  m = min(
    abs(s),
    min(v[i] + (abs(psumt[i] - s) + abs(psumt[i+1] - s) - t[i]) / 2 for i in range(N)),
    abs(T-s)
  )
  ans += m / 2
print('%.9f' % ans)

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

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

INF = float('inf')
V = [INF for i in range(2*T[n-1]+1)]

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

for vi in range(n):
    for ti in range(2*T[n-1]+1):
        if vi == 0:
            if ti <= T[0] * 2:
                V[ti] = min(V[ti], v[0])
            else:
                V[ti] = min(V[ti], v[0] + ti * 0.5 - T[0])
        else:
            if ti <= T[vi-1] * 2:
                V[ti] = min(V[ti], v[vi] + T[vi-1] - ti * 0.5)
            elif (T[vi-1] * 2 <= ti) and (ti <= T[vi] * 2):
                V[ti] = min(V[ti], v[vi])
            else:
                V[ti] = min(V[ti], v[vi] + (ti * 0.5 - T[vi]))

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

print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

def trapezoid(St, En, H, i):
    if St+H[i][0] >= En-H[i][0]:
        return (En-St)**2/4
    result = H[i][0]*(En-St-H[i][0])
    if H[i][1] > St + H[i][0]:
        result += trapezoid(St+H[i][0],min(En-H[i][0],H[i][1]),H,i+1)
    if H[i][2] < En - H[i][0]: 
        result += trapezoid(max(St+H[i][0],H[i][2]),En-H[i][0],H,i+1)       
    return result

N = int(input())
t = inpl()
v = inpl()
H = [[v[0], 0, t[0]]]
for i in range(1,N):
    H.append([v[i], H[i-1][2], H[i-1][2]+t[i]])

H.append([float('inf'), 0, 0])
H.sort(key = lambda x: x[0])
for i in range(N,0,-1):
    H[i][0] -= H[i-1][0]    
print(trapezoid(0,sum(t), H, 0))

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

m = sum(t)
d = [0 for _ in range(m + 1)]

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

ans = 0
v = 0
s = m
for i in range(n - 1, -1, -1):
    for j in range(t[i]):
        d[s] = v
        if v == d[s - 1] and v < L[i]:
            ans += 0.25
        v = min(v + 1, L[i], d[s - 1])
        s -= 1

for i in range(1, m + 1):
    if d[i] == d[i - 1]:
        ans += d[i]
    elif d[i] > d[i - 1]:
        ans += d[i] - 0.5
    elif d[i] < d[i - 1]:
        ans += d[i] + 0.5
    

print(ans)

Solution (Python):
N = int(input())
t = list(map(int,input().split()))
vlist = list(map(int,input().split()))
import numpy as np
t = np.cumsum(np.array(t))
T = t[-1]
def line(tl,tr,v):
    leq = np.arange(2*T+1)/2
    leq[:2*tl+1] *= -1
    leq[:2*tl+1] += tl
    leq[2*tl+1:2*tr+1] *= 0
    leq[2*tr+1:] -= tr
    leq += v
    return leq

f = np.zeros((N+2)*(2*T+1)).reshape((N+2,2*T+1))
for i in range(N):
    if i != 0:
        tl = t[i-1]
    else:
        tl = 0
    tr = t[i]
    v = vlist[i]
    f[i] = line(tl,tr,v)
f[N]=line(0,0,0)
f[N+1]=line(T,T,0)
v = f.min(0)

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

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


tt = 0
lim = []

for i in range(N):
    for j in range(ts[i]):
        lim.append(vs[i])
        tt += 1

up = [False for i in range(tt)]
v = 0
for i in range(tt):
    if lim[i] > v:
        v += 1
        lim[i] = v
        up[i] = True
    else:
        v = lim[i]

down = [False for i in range(tt)]
v = 0
for i in range(tt - 1, -1, -1):
    if lim[i] > v:
        v += 1
        if lim[i] > v:
            up[i] = False
        lim[i] = v
        down[i] = True
    else:
        v = lim[i]

ans = 0
for i in range(tt):
    ans += lim[i]
    if up[i] and down[i]:
        ans -= 0.75
    elif up[i] or down[i]:
        ans -= 0.5
    
print(ans)

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

t = [0] + t
for i in range(N):
    t[i + 1] += t[i]

y = [0] * (t[N] * 2 + 1)

for i, (t1, t2) in enumerate(zip(t, t[1:])):
    for x in range(2 * t1, 2 * t2):
        y[x + 1] = min(v[i], y[x] + 0.5)

y[2 * t[N]] = 0
for i, (t1, t2) in enumerate(zip(t[::-1], t[::-1][1:])):
    for x in range(2 * t1, 2 * t2, -1):
        y[x - 1] = min(y[x - 1], v[N - i - 1], y[x] + 0.5)

print(sum((y[i] + y[i + 1]) * 0.5 for i in range(t[N] * 2)) / 2)

Solution (Python):
N = int(input())
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))
 
maxv = [0] * (sum(ts) * 2 +1)
dp = [0] * (sum(ts) * 2 + 1)
ima = 1
for i in range(len(ts)):
  k = ts[i]
  if i != 0:
    maxv[ima-1] = min(vs[i],vs[i-1])
  for j in range(k*2):
    maxv[j+ima] = vs[i]
  ima  += k*2
maxv[-1] = 0
for i in range(1,len(dp)):
  dp[i] = min(dp[i-1] + 0.5,maxv[i])
for i in range(len(dp)-1,0,-1):
  dp[i-1] = min(dp[i] + 0.5,maxv[i-1],dp[i-1])
ans = sum(dp)/2
print(ans)

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

from itertools import accumulate

n = ni()
t = [0] + list(li())
v = [0] + list(li()) + [0]

t_acc = list(accumulate(t))
t_max = t_acc[-1]
t_cur = [10**10]*(2*t_max+1)

interval = dict({(0,0): 0, (t_max,t_max): 0})
for i in range(n):
    interval.update({(t_acc[i], t_acc[i+1]): v[i+1]})
    
for t_idx in range(2*t_max+1):
    for i, ((tl,tr), v) in enumerate(interval.items()):
        
        if t_idx*0.5 < tl:
            t_cur[t_idx] = min(t_cur[t_idx], abs(v+(tl-t_idx*0.5)))
            
        elif tl <= t_idx*0.5 <= tr:
            t_cur[t_idx] = min(t_cur[t_idx], v)
            
        elif tr < t_idx*0.5:
            t_cur[t_idx] = min(t_cur[t_idx], abs(v+(t_idx*0.5-tr)))

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

print(ans)

Solution (Python):
def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    a = []
    for i in t:
        a.append(i * 2)
    t = a
    v = list(map(int, input().split()))
    
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 0.5
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 0.5, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    
    ans = 0
    for i in speed_list:
        ans += i

    print(ans / 2)
ABC076D()

Solution (Python):
def main():

    S = list(input())
    checklist = [0 for i in range(26)]
    for i in S:
        checklist[ord(i) - ord("a")] += 1
    ans = True

    for i in checklist:
        if i > 1:
            ans = False

    if not ans:
        print(-1)
        return 0
    else:
        ans = False
        for i in range(len(checklist)):
            if checklist[i] == 0:
                for i in S:
                    print(i, end="")
                print(chr(i + ord("a")), end = "")
                print()
                ans = True
                break

        if not ans:
            new_S = []
            for i in S:
                new_S.append(ord(i))

            for i in range(len(new_S) - 1):
                if new_S[i] > new_S[i + 1]:
                    for j in range(i - 1):
                        print(S[j], end = "")
                    print(chr(new_S[i - 1] + 1), end = "")
                    print()
                    ans = True
                    break

            if not ans:
                print(-1)


def ABC069D():

    H, W = map(int, input().split())
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(N):
        for j in range(a[i]):
            ans.append(i + 1)
    printlist = [[0 for i in range(W)] for j in range(H)]
    k = 0
    for i in range(H):
        for j in range(W):
            printlist[i][j] = ans[k]
            k += 1
        if i % 2 != 0:
            printlist[i] = printlist[i][::-1]

    for i in range(H):
        for j in range(W):
            print(printlist[i][j], end = "")
            if j != W:
                print(" ", end = "")
        print()
    print()


import math
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def ABC057D():

    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    v = sorted(v)[::-1]

    anslist = []
    for i in range(A, B + 1):

        anslist.append([sum(v[0:i]) / i, i, v[i - 1]])
    anslist.sort()
    anslist = anslist[::-1]
    ans = anslist[0][0]
    key = anslist[0][2]
    long = anslist[0][1]
    print(ans)
    for i in range(1, len(anslist)):
        if anslist[i][0] == anslist[i - 1][0]:
            ans = anslist[i][0]
            key = anslist[i][2]
            long = anslist[i][1]
        else:
            break
    
    
    cnt = 0
    for i in v:
        if i == key:
            cnt += 1

    c = 0
    for i in v[:long]:
        
        if i == key:
            c += 1
    
    ans = 0
    if c == long:
        for i in range(A,  min(B + 1, cnt + 1)):
            ans += cc(cnt, i)
    else:
        ans = cc(cnt, c)
    
    
    print(ans)


def ABC104D():
    S = list(input())
    A_cnt = 0
    B_cnt = 0
    C_cnt = 0
    Q_cnt = 0
    ans = 0
    for i in S:
        if i == "A":
            A_cnt += 1
        elif i == "B":
            B_cnt += 1
        elif i == "C":
            C_cnt += 1
        else:
            Q_cnt += 1
    for i in range(Q_cnt + 1):
        for j in range(Q_cnt - i + 1):
            k = Q_cnt - i - j
            if A_cnt + i > 0 and B_cnt + j > 0 and C_cnt + k > 0:
                f_i = math.factorial(i)
                f_j = math.factorial(j)
                f_k = math.factorial(k)
                if f_i == 0:
                    f_i = 1
                if f_j == 0:
                    f_j = 1
                if f_k == 0:
                    f_k = 1
                ans += (A_cnt + i) * (B_cnt + j) * (C_cnt + k) * math.factorial(Q_cnt) // f_i // f_j // f_k
                print(ans, i, j, k, A_cnt + i, B_cnt + j, C_cnt + k)
                print(math.factorial(Q_cnt), f_i, f_j, f_k)
    print(ans)


def ARC073D():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

def ARC075():
    N, A, B = map(int, input().split())
    h = [int(input()) for i in range(N)]
    def enogth(T):
        import copy
        this_h = copy.copy(h)
        cnt = 0
        for i in range(N):
            this_h[i] -= B
            key = 0
            if this_h[i] > 0:
                key = this_h[i] / (A - B)
                if int(key) != key:
                    key += 1
                cnt += int(key)
        if cnt <= T:
            return True
        else:
            return False
    def sarch(i: object) -> object:
        print(i)
        if enogth(i):
            if i // 2 == 1:
                return i
            sarch(0 + i // 2)
        else:
            sarch(i + i // 2)
    print(sarch(10 ** 9))


def ARC082D():
    N = int(input())
    p = list(map(int, input().split()))
    cnt = 0
    if p[N - 1] == N:
        
        p[-2], p[-1] = p[-1], p[-2]
        cnt += 1

    for i in range(N - 1):
        if p[i] == i + 1:
            p[i], p[i + 1] = p[i + 1], p[i]
            cnt += 1
    print(cnt)



from queue import Queue
def ABC070D():
    N = int(input())
    a, b, c =map(int, input().split())
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    x = [[] for i in range(N)]
    for i, j in xy:
        x[i - 1].append(j - 1)
        x[j - 1].append(i - 1)

    q = Queue()
    visited = [0 for i in range(N)]


def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    print(speed_lim)
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 1
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 1, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans)


def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    a = []
    for i in t:
        a.append(i * 2)
    t = a
    v = list(map(int, input().split()))
    
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 0.5
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 0.5, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    
    ans = 0
    for i in speed_list:
        ans += i

    print(ans / 2)
ABC076D()

Solution (Python):


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

e = sum(t)*2
vmax = [0 for k in range(e+2)]

s = 0
for k in range(N):
    for l in range(1,t[k]*2+1):
        vmax[s+l] = v[k]
    s += t[k]*2

hidari = [0 for k in range(e+1)]
for k in range(1,e+1):
    hidari[k] = min(hidari[k-1]+0.5,vmax[k])

migi = [0 for k in range(e+1)]
for k in range(1,e+1):
    migi[e-k] = min(migi[e-k+1]+0.5,vmax[e-k+1])

ans = 0
for k in range(e+1):
    ans += min(hidari[k],migi[k])
print(ans/2)

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

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

v_max = [0]    
idx = 0
for i in range(1, 2*sum(t)+1):
    time = i/2
    if time < t_cumsum[idx]:
        v_max.append(v[idx])
    elif time == t_cumsum[-1]:
        v_max.append(0)
    else:
        v_max.append(min(v[idx], v[idx+1]))
        idx += 1

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


ans = 0
for v0, v1 in zip(vs[:-1], vs[1:]):
    ans += (v0+v1)/2*0.5
print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


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


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    end = 2 * sum(T)

    H = [INF] * (end + 10)
    now = 0
    for i, t in enumerate(T):
        for j in range(now, (now + t * 2) + 1):
            H[j] = min(H[j], V[i])
        now = now + t * 2

    H[0] = 0.0
    H[end] = 0.0
    for i in range(end):
        H[i + 1] = min(H[i + 1], H[i] + 1 / 2)
    for i in range(end, 0, -1):
        H[i - 1] = min(H[i - 1], H[i] + 1 / 2)

    ans = 0
    for i in range(end):
        ans += (H[i] + H[i + 1]) * 0.5 * (1/2)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


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


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    base = 2
    end = base * sum(T)

    H = [INF] * (end + 10)
    now = 0
    for i, t in enumerate(T):
        for j in range(now, (now + t * base) + 1):
            H[j] = min(H[j], V[i])
        now = now + t * base

    H[0] = 0.0
    H[end] = 0.0
    H[end + 1] = 0.0
    for i in range(end + 1):
        H[i + 1] = min(H[i + 1], H[i] + 1 / base)
    for i in range(end, 0, -1):
        H[i - 1] = min(H[i - 1], H[i] + 1 / base)

    
    
    ans = 0
    pre_i, pre_mode = 0, 1
    for i in range(end + 1):
        if H[i] < H[i + 1]:
            mode = 0
        elif H[i] == H[i + 1]:
            mode = 1
        else:
            mode = 2

        if mode != pre_mode:
            
            ans += (H[pre_i] + H[i]) * ((i - pre_i) / base) * (1/2)
            pre_i, pre_mode = i, mode

    print(ans)


if __name__ == '__main__':
    main()

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

ans = 0
prev_spped = 0

for x in range(1, 2 * t[-1] + 1):
	time = x / 2
	speeds = [time, t[-1] - time]
	for i in range(n):
		if time <= t[i]:
			speeds.append(v[i] + t[i] - time)
		elif t[i] < time <= t[i + 1]:
			speeds.append(v[i])
		else:
			speeds.append(v[i] + time - t[i + 1])
	speed = min(speeds)
	ans += (speed + prev_spped) * 0.25
	prev_spped = speed

print(ans)

Solution (Python):
from itertools import accumulate as ac
o=[]
f=lambda l,r,v:lambda x:v if l<=x<=r else v+(l-x) if 0<=x<=l else v+(x-r)

o.extend([f(0,0,0)])
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())
*c,=ac([0]+a)

for (i,(t,v)) in enumerate(zip(a,b)):
  o.extend([f(c[i],c[i+1],v)])
o.extend([f(c[-1],c[-1],0)])
v=lambda s:min(map(lambda x:x(0.5*s),o))

S=0
for i in range(2*c[-1]):
  S+=0.25*(v(i)+v(i+1))
print(S)

Solution (Python):
'''
38分あたり
https://www.youtube.com/watch?v=T1zXzsoK268
'''
def input_num_list(): return list(map(int, input().split()))

n = int(input())
t = input_num_list()
T = sum(t)
v = input_num_list()
maxv = [100 for _ in range(2 * T + 1)]
maxv[0] = 0
maxv[2 * T] = 0

t_l, t_r = 0, 0
for i in range(n):
    t_l = t_r
    t_r += t[i]
    vv = v[i]
    for j in range(2 * t_l, 2 * t_r + 1):
        maxv[j] = min(maxv[j], vv)


i = 1
while i <= 2 * T:
    maxv[i] = min(maxv[i], maxv[i - 1] + 0.5)
    i += 1

i = 2 * T - 1
while i >= 0:
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)
    i -= 1

ans = 0
i = 0
while i <= 2 * T - 1:
    ans += 0.25 * (maxv[i] + maxv[i + 1])
    i += 1
    
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)
T = len(maxv)
 
for i in range(T-1):
    maxv[i+1] = min(maxv[i+1], maxv[i] + 0.5)
 
maxv[-1] = 0
for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i+1] + 0.5)
 
ans = 0.0
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)

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

V = [0] + V + [0]



left = [0]
right = [0]

for i in range(N):
    left.append(right[i])
    right.append(left[-1]+T[i])
    
left.append(right[-1])
right.append(right[-1])

INF = float("inf")
vel = [INF]*(2*right[-1]+1)


for t in range(2*right[-1]+1):
    for i in range(N+2):
        if (t/2) < left[i]:
            vel[t] = min(vel[t], -(t/2)+(V[i]+left[i]))
        elif left[i] <= (t/2) and (t/2) <= right[i]:
            vel[t] = min(vel[t], V[i])
        elif (t/2) > right[i]:
            vel[t] = min(vel[t], (t/2)+(V[i]-right[i]))
            


ans = 0
for t in range(2*right[-1]):
    ans += (1/2)*0.5*(vel[t]+vel[t+1])
    
print(ans)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

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

upper = []

Ts = 0
for i in range(N):
    upper.append((Ts, V[i]))
    Ts += T[i]
    upper.append((Ts, V[i]))

S = sum(T)
upper.append((0, 0))
upper.append((S, 0))

ans = [0]
Ts = 0
for i in range(N):
    dt = 0
    while True:
        dt += 0.5
        t = Ts + dt
        v = V[i]
        for p in upper:
            v = min(v, p[1] + abs(p[0] - t))
        ans.append(v)
        if dt == T[i]:
            break
    Ts += T[i]

print (sum(ans[1:]) + sum(ans[:-1])) / 4

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, T, V):

    T.append(0)
    V.append(0)

    df = 0.5
    
    vs = [0] * int(sum(T)*(1/df) + 2)

    i = 1
    for t, v in zip(T, V):
        
        if vs[i-1] > v:
            j = 0
            while abs(vs[i-1-j] - vs[i-1-j+1]) > 0.001:
                vs[i-1-j] = min(vs[i-1-j], v + j*df)
                j += 1

        for _ in range(t*int(1/df)):
            vs[i] = min(vs[i-1]+df, v)
            i += 1

    ans = 0
    for i in range(len(vs)-1):
        d = vs[i+1] - vs[i]
        ans += vs[i]*df
        ans += (d*df)/2

    
    
    
    return ans


def main():
    N = read_int()
    T = read_int_n()
    V = read_int_n()

    print(slv(N, T, V))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
T = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]
T.append(0)
V.append(0)
Vt = [0 for i in range(N + 1)]
r = sum(T)
R = [0 for i in range(N)]
for i in range(N - 1):
  r -= T[i]
  R[i] = r
for i in range(N - 1, -1, -1):
  Vt[i] = min(V[i], V[i + 1], Vt[i + 1] + T[i + 1])
L = 0
v0 = 0
for i in range(N):
  ta = min(V[i] - v0, (T[i] - (v0 - Vt[i])) / 2, T[i])
  tb = max(v0 + ta - Vt[i], 0)
  L += (2 * v0 + ta) * ta / 2 + (v0 + ta) * (T[i] - ta - tb) + (2 * (v0 + ta) - tb) * tb / 2
  v0 = v0 + ta - tb
print(L)

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())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))


accTs = list(accumulate(ts))
sumT = accTs[-1]
vMaxs = [[] for i in range(N + 2)]
for i, (v, l, r) in enumerate(zip(vs + [0, 0], [0] + accTs[:-1] + [0, sumT], accTs + [0, sumT])):

    vms = [v + l - t / 2 for t in range(0, l * 2)] + \
          [v] * ((r - l) * 2 + 1) + \
          [v + t / 2 - r for t in range(r * 2 + 1, sumT * 2 + 1)]

    vMaxs[i] = vms


vMaxs = list(map(min, *vMaxs))

print(sum(vMaxs) / 2)

Solution (Python):
from bisect import bisect_left
n = int(input())
t = [0]+[int(i) for i in input().split()]+[0]
v = [int(i) for i in input().split()]+[0]
def f(x,v,t1,t2):
	if x<t1: return v+(t1-x)
	elif t1<=x<=t2: return v
	else: return v+(x-t2)
for i in range(1,n+2): t[i]+=t[i-1]
T,ans = t[-1],0
for i in range(2*T+1):
	num = min(i/2,T-i/2)
	for j in range(max(0,bisect_left(t,i/2-100)-1),n+1):
		if i/2<t[j]-100: break
		num = min(num,f(i/2,v[j],t[j],t[j+1]))
	ans+=num/2
print(ans)

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

bound = [0 for _ in range(N+1)]

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


sum=0
for i in range(N):
    if (bound[i]+bound[i+1]+t[i])/2>v[i]:
        sum+=(bound[i]+v[i])*(v[i]-bound[i])/2
        sum+=(bound[i+1]+v[i])*(v[i]-bound[i+1])/2
        sum+=v[i]*(t[i]-2*v[i]+bound[i]+bound[i+1])
    else:
        sum+=(bound[i+1]-bound[i]+t[i])*0.5*(bound[i+1]+3*bound[i]+t[i])*0.5*0.5
        sum+=(t[i]+bound[i]-bound[i+1])*0.5*(bound[i]+3*bound[i+1]+t[i])*0.5*0.5

print(sum)

Solution (Python):
N = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))
v = [0]*(sum(T)*2+1)
t,Ti = 0,0
for i in range(N):
    Ti += T[i]*2
    v[t] = min(v[t],V[i])
    while t < Ti:
        if v[t] < V[i]:
            v[t+1] = v[t]+0.5
        else:
            v[t+1] = min(v[t],V[i])
        t += 1
sumT = sum(T)*2
v[sumT] = 0
t,Ti = sumT,sumT
for i in range(N):
    Ti -= T[N-i-1]*2
    while t > Ti:
        if v[t-1] > v[t]+0.5:
            v[t-1] = v[t]+0.5
        t -= 1
Ans = 0
for i in range(sumT):
    Ans += (v[i]+v[i+1])*0.5/2

print(Ans)