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



Sample input:
1
100
30


Sample output:
2100.000000000000000

Submission status: Accepted

Solution code:
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
vs.append(0)

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

ds = [[-1 for _ in range(101)] for _ in range(2)]
ds[0][0] = 0
i = 0
for t in range(1, ss[-1] + 1):
    vl = vs[i]
    ve = vs[i]
    if t == ss[i]:
        i += 1
        ve = min(ve, vs[i])
    for v in range(101):
        ds[t % 2][v] = -1
        if 0 <= ds[(t - 1) % 2][v]:
            if v < vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + 4 * v + 1
            elif v == vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + 4 * v
    for v in range(1, 101):
        if 0 <= ds[(t - 1) % 2][v] and v <= vl and v - 1 <= ve:
            ds[t % 2][v - 1] = max(ds[t % 2][v - 1], ds[(t - 1) % 2][v] + 4 * v - 2)
    for v in range(100):
        if 0 <= ds[(t - 1) % 2][v] and v < vl and v + 1 <= ve:
            ds[t % 2][v + 1] = max(ds[t % 2][v + 1], ds[(t - 1) % 2][v] + 4 * v + 2)

print(ds[ss[-1] % 2][0] / 4)

Submission status: Accepted

Solution code:

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

def interval(t):
    pass

N=int(input())
T=spaceinput()
v=spaceinput()

Tmax=0

for i in range(N):
    Tmax+=(T[i])
#mv=[0]*(Tmax+1)
mv={}

frange=[x for x in range(2*Tmax+1)]

k=0
sT=T[0]
d=0.5

mv[0]=0
for t in [x/2 for x in range(1,2*Tmax)]:

    if sT<t:
        k+=1
        if k<len(T):
            sT+=T[k]
        else:
            break

    mv[t]=min(v[k],mv[t-0.5]+d)

mv[Tmax]=0

k=N-1
sT=Tmax-T[-1]
for t in reversed([x/2 for x in range(1,2*Tmax)]):
    if sT>t:
        k-=1
        sT-=T[k]

    mv[t]=min(v[k],mv[t],mv[t+d]+d)


res=0
k=0
sT=T[0]
for t in [x/2 for x in range(1,2*Tmax)]:
    if sT<t:
        if t==Tmax-1:
            break
        k+=1
        if k<len(T):
            sT+=T[k]
    res+=mv[t]*0.5

print(res)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
ans = 0

bound = [0] * (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], v[i], v[i-1], bound[i+1] + t[i])
 
ans = 0
for i in range(n):
    l = bound[i]
    r = bound[i+1]
    x = (r-l+t[i])/2
    if l + x <= v[i]:
        ans += (l + (l + x)) * x / 2 + (l + x + r) * (t[i] - x) / 2
    else:
        ans += (v[i] + l) * (v[i] - l) / 2 + (v[i] + r) * (v[i] - r) / 2
        ans += (t[i] - (v[i] - l) - (v[i] - r)) * v[i]
print("{:.14f}".format(ans))

Submission status: Accepted

Solution code:
n = int(input())
t_list = input().split()
t_list = [int(t) for t in t_list]
v_list = input().split()
v_list = [int(v) for v in v_list]


down_list = []
v_list.append(0)
for i in range(n):
    down = []
    down.append(sum(t_list[:i+1]))
    down.append(min(v_list[i],v_list[i+1]))
    down_list.append(down)
    
now_v = 0
distance = 0
kukan = 0
down_check = 0
now_s = 0
last_time = down_list[-1][0]
while now_s < last_time:
    for down in down_list[kukan:]:
        if down[1]+(down[0]-now_s)*1==now_v:
            next_s = down_list[kukan][0]
            next_v = now_v +(-1*(next_s-now_s))
#             print("4",next_s,next_v,now_s,now_v)
            distance += (next_v +now_v) * (next_s-now_s) /2
#             print("1",now_s,now_v,distance)
            now_v = next_v
            now_s = next_s
            kukan += 1
            down_check = 1
            break
    if down_check == 1:
        down_check = 0
        continue
    else:
        if now_v == v_list[kukan]:
            distance += now_v * 0.5
#             print("2",now_s,now_v,distance)
        else:
            next_v = now_v + 0.5
            distance += (next_v + now_v) * 0.5 /2
#             print("3",now_s,now_v,distance)
            now_v = next_v

        now_s += 0.5
        if kukan < len(down_list):
            if now_s == down_list[kukan][0]:
                kukan += 1
#                 print("kukan",kukan)

print(distance)

Submission status: Accepted

Solution code:
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)
va[-1] = 0

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

Submission status: Accepted

Solution code:
N = int(raw_input())
ts = map(int, raw_input().split())
vs = map(int, raw_input().split())

vs.append(0)

for i in xrange(N-1, -1, -1):
  vs[i] = min(vs[i], vs[i+1] + ts[i])

def dist(vstart, vend, time):
  return time * (min(vstart, vend) + (abs(vstart - vend) / 2.0))

v = 0
ans = 0.0
for i in xrange(N):
  a = min(ts[i], vs[i] - v)
  vs[i] = min(vs[i], v + a)
  b = max(0, vs[i] - vs[i+1]) # <= ts[i]
  c = ts[i] - a - b
  #print i, v, vs[i], ts[i], '   ', a, c, b

  if c >= 0:
    ans += dist(v, vs[i], a) + dist(vs[i], vs[i], c) + dist(vs[i], vs[i+1], b)
  else:
    a, b = (a-b+ts[i])/2.0, (b-a+ts[i])/2.0
    ans += dist(v, v+a, a) + dist(v+a, v+a-b, b)

  v = v + a - b

print ans

Submission status: Accepted

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

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
d_int = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	rest_t = [T[i]-now_t for i in range(N)]
	if now_v < v[now_n]:
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif now_v == v[now_n]: 
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 0
	for i in range(N):
		rest = rest_t[i]
		if rest > 0:
			d_v = now_v - v[i+1]
			if rest == d_v:
				a = -1

	d_int += 2 * int(now_v * 2) + a
	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d)

Submission status: Accepted

Solution code:
N = input()
t = map(int, raw_input().split())
v = map(int, raw_input().split())
v1 = [0]*N
v2 = [0]*N
for i in range(1,N):
    v1[i] = min(v1[i-1]+t[i-1], v[i-1], v[i])
for i in range(N-1)[::-1]:
    v2[i] = min(v2[i+1]+t[i+1], v[i+1], v[i])
for i in range(N):
    v1[i] = min(v1[i], v2[i]+t[i])
    v2[i] = min(v1[i]+t[i], v2[i])
ans = 0
for i in range(N):
    vm = min((v1[i]+v2[i]+t[i])*.5, v[i]*1.)
    ans += (vm-v1[i])**2*.5 + (vm-v1[i])*v1[i] + (vm-v2[i])**2*.5 + (vm-v2[i])*v2[i] + vm*(t[i]-(vm-v1[i])-(vm-v2[i]))
print "%.10f"%ans

Submission status: Accepted

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

sumT = sum(ts)
va = [min(i / 2, sumT - i / 2) for i in range(2 * sumT + 1)]

accT = 0
for t, v in zip(ts, vs):
    for i in range(accT, accT + 2 * t + 1):
        va[i] = min(va[i], v)
    accT += t * 2

for i in range(len(va) - 1):
    if va[i + 1] - va[i] > 0.5:
        va[i + 1] = va[i] + 0.5

for i in range(len(va) - 1)[::-1]:
    if va[i] - va[i + 1] > 0.5:
        va[i] = va[i + 1] + 0.5

print(sum(va) / 2)

Submission status: Accepted

Solution code:
N = int(input())
tt = map(int, input().split())
vv = map(int, input().split())

v_now = 0
v_max = [v_now]
for t, v in reversed(list(zip(tt, vv))):
    for i in range(t * 2):
        if v_now + 0.5 <= v:
            v_now += 0.5
        else:
            v_now = min(v_now, v)
        v_max.append(v_now)
v_max = v_max[::-1]

v = 0
total = 0
for i in range(len(v_max) - 1):
    v0 = v_max[i]
    v1 = v_max[i+1]
    if v + 0.5 <= v1:
        if v < v0:
            total += (v + v + 0.5) * 0.25
            v += 0.5
        else:
            total += v * 0.5
    elif v > v1:
        total += (v + v - 0.5) * 0.25
        v -= 0.5
        assert v == v1, '%s %s'%(v,v1)
    else:
        total += v * 0.5
print(total)

Submission status: Accepted

Solution code:
from fractions import Fraction as F

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

VL = [V[i] for i in xrange(N)]
VL.append(0)
for i in xrange(N-1, -1, -1):
    VL[i] = min(VL[i], VL[i+1] + T[i])

v1 = F(0)
v2 = F(0)
ans = F(0)

for i in xrange(N):
    t1 = F(0)
    v2 = F(v1)

    while t1 < T[i] and v2 < V[i] and v2 - (T[i] - t1) < VL[i+1]:
        t1 += F(1, 2)
        v2 += F(1, 2)
    v2 = v1 + t1
    ans += (v1 + v2) / F(2) * t1

    t2 = F(0)
    while t1 + t2 < T[i] and v2 - (T[i] - t1 - t2) < VL[i+1]:
        t2 += F(1, 2)
    ans += v2 * t2

    v3 = v2 - (T[i] - t1 - t2)
    ans += (v2 + v3) / F(2) * (T[i] - t1 - t2)

    v1 = v3

print "%.09f" % ans

Submission status: Accepted

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

VL = [V[i] for i in xrange(N)]
VL.append(0)
for i in xrange(N-1, -1, -1):
    VL[i] = min(VL[i], VL[i+1] + T[i])

v1 = 0
v2 = 0
ans = 0

for i in xrange(N):
    t1 = 0
    v2 = v1

    hi = T[i] * 1.0
    lo = 0
    for _ in xrange(100):
        mid = (hi + lo) / 2
        tt = t1 + mid
        vv = v2 + mid
        if tt <= T[i] and vv <= V[i] and vv - (T[i] - tt) <= VL[i+1]:
            lo = mid
        else:
            hi = mid

    t1 += hi
    v2 = v1 + t1
    ans += (v1 + v2) / 2.0 * t1

    hi = (T[i] - t1) * 1.0
    lo = 0
    for _ in xrange(100):
        mid = (hi + lo) / 2
        tt = mid
        if t1 + tt <= T[i] and v2 - (T[i] - t1 - tt) < VL[i+1]:
            lo = mid
        else:
            hi = mid

    t2 = hi
    ans += v2 * t2

    v3 = v2 - (T[i] - t1 - t2)
    ans += (v2 + v3) / 2.0 * (T[i] - t1 - t2)

    v1 = v3

print "%.09f" % ans

Submission status: Accepted

Solution code:
n = int(input())
ts = [int(c) for c in input().split()]
vs = [int(c) for c in input().split()]

t = sum(ts)
dp = [[-10 ** 10 for _ in range(101)] for _ in range(t + 1)]
dp[0][0] = 0.

mvs = []
for dt, mv in zip(ts, vs):
    for st in range(dt):
        mvs.append(mv)
mvs.append(0)

for ct in range(t):
    mv = mvs[ct]
    for cv in range(mv + 1):
        endmv = min(mv, mvs[ct+1])
        for dv in [-1, 0, 1]:
            nv = cv + dv
            if 0 <= nv <= endmv:
                dp[ct + 1][nv] = max(dp[ct][cv] + (cv + nv) / 2, dp[ct + 1][nv])
        if mv >= cv + 1 and cv <= endmv:
            dp[ct + 1][cv] = max(dp[ct+1][cv], dp[ct][cv] + cv + 0.25)


print(dp[t][0])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    t = LI()
    u = LI()
    a = [inf] * n
    b = [inf] * n
    a[0] = 0
    b[0] = min(t[0],u[0])
    b[-1] = 0
    a[-1] = min(a[-1],t[-1],u[-1])
    for i in range(1,n):
        a[i] = min(a[i],b[i-1],u[i])
        b[i] = min(b[i],a[i]+t[i],u[i])
    for i in range(n-2,-1,-1):
        b[i] = min(b[i],a[i+1],u[i])
        a[i] = min(a[i],b[i]+t[i],u[i])
    r = 0
    for i in range(n):
        c = a[i]
        d = b[i]
        e = u[i]
        f = t[i]
        k = abs(c-d)
        m = max(c,d)
        l = min(m + (f-k) / 2.0,e)
        ct = l-c
        r += c*ct + ct*(l-c) / 2.0
        dt = l-d
        r += d*dt + dt*(l-d) / 2.0
        r += l * (f-ct-dt)

    return r


print(main())

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
t = na()
v = na()

bound = [0] * (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], v[i], v[i-1], bound[i+1] + t[i])

ans = 0
for i in range(n):
    l = bound[i]
    r = bound[i+1]
    # l + x = r + t - x
    # x = (r-l+t)/2
    x = (r-l+t[i])/2
    if l + x <= v[i]:
        ans += (l + (l + x)) * x / 2 + (l + x + r) * (t[i] - x) / 2
    else:
        ans += (v[i] + l) * (v[i] - l) / 2 + (v[i] + r) * (v[i] - r) / 2
        ans += (t[i] - (v[i] - l) - (v[i] - r)) * v[i]
print("{:.14f}".format(ans))

Submission status: Runtime Error

Solution code:
import sys
from collections import *
import heapq
import math
from math import gcd
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])
        # print(l,r)
    lst[i+1]=min(tmp)

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

su = sum(t)
a = [min(i, su - i) for i in range(su + 1)]

cnt = 0
for t_i, v_i in zip(t, v):
    for i in range(cnt, cnt + t_i + 1):
        a[i] = min(a[i], v_i)
    cnt += t_i

for i in range(su):
    a[i + 1] = min(a[i + 1], a[i] + 1)

for i in range(su)[-1]:
    a[i] = min(a[i], a[i + 1] + 1)

print(sum(a) / 4)

Submission status: Runtime Error

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

su = sum(t)
a = [min(i, su - i) for i in range(su + 1)]

cnt = 0
for t_i, v_i in zip(t, v):
    for i in range(cnt, cnt + t_i + 1):
        a[i] = min(a[i], v)
    cnt += t_i

for i in range(su):
    a[i + 1] = min(a[i + 1], a[i] + 1)

for i in range(su)[-1]:
    a[i] = min(a[i], a[i + 1] + 1)

print(sum(a) / 4)

Submission status: Runtime Error

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

su = sum(t)
a = [min(i, su - i) for i in range(su + 1)]

cnt = 0
for t_i, v_i in zip(t, v):
    for i in range(cnt, cnt + t_i + 1):
        a[i] = min(a[i], v)
    cnt += t_i

for i in range(su):
    a[i + 1] = min(a[i + 1], a[i] + 1)

for i in range(su)[-1]:
    a[i] = min(a[i], a[i + 1] + 1)

print(sum(a) / 4)

Submission status: Runtime Error

Solution code:
N=int(input())
T=[0]+[int(x) for x in str(input()).split()]+[0]
V=[0]+[int(x) for x in str(input()).split()]+[0]
time=0
t=[0]
for i in T:
  time+=i
  t.append(time)
ans=0

for j in range(0,2*time):
  m2=100000000
  m1=100000000
  t1=j/2
  t2=(j+1)/2
  print(t1,t2)
  for i in range(N+2):
	a=t[i]
	b=t[i+1]
	c=V[i]
    if t1<=a:
      m1=min(m1,c+(a-t1))
    elif t1<=b:
      m1=min(m1,c)
    else:
      m1=min(m1,c+t1-b)

    if t2<=a:
      m2=min(m2,c+(a-t2))
    elif t2<=b:
      m2=min(m2,c)
    else:
      m2=min(m2,c+t2-b)
    
  ans+=0.25*(m1+m2)
print(ans)

Submission status: Runtime Error

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

for i in range(N-1,-1,-1):
  v=V[i+1]
  t=T[i]
  V[i]=min(V[i],v+t)
  
v=0
ans=0
for i in range(N):
  t_p=T[i]
  v_p=V[i]
  v_a=V[i+1]
  if v_p==v_a:
    if v==v_p:
      ans+=t_p*v_p
      v=v_a
    elif v_a-v>=t_p:
      ans+=
      v=v_a
  elif v_p<v_a:
    ans+=max(t_p-(v_p-v),0)*v_p+min(t_p,v_p-v)*(v+v_p)/2
    v=min(v_p,v+t_p)
  else:
    if t_p>=(v_p-v)+(v_p-v_a):
      ans+=(v_p-v_a)*(v_p+v_a)/2 + (v_p-v)*(v+v_p)/2 + v_p*(t_p-(v_p-v)-(v_p-v_a))
      v=v_a
    else:
      vx=(t_p+v+v_a)/2
      ans+=(vx+v)*(vx-v)/2+(vx+v_a)*(vx-v_a)/2
      v=v_a
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
t = [0] + list(map(int, input().split()))
v = [0] + list(map(int, input().split()))
max_speed_from_left = [0] * (N + 1) #index i = t[i] とt[i + 1]の間
max_speed_from_right = [0] * (N + 1) #index i = t[i] とt[i + 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 = 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
    #最高速度vに到達してt-x余る
    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)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0

if n==1:
    if a[0]>=b[0]*2:
        print(b[0]**2+b[0]*(a[0]-b[0]*2))
    else:
        print(a[0]/2**2)
else:
    for i in range(n):
        if i==n-1:

Submission status: Runtime Error

Solution code:
import numpy as np

N=int(input())

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

tsum=np.sum(t)
print(tsum)

Ruisekit=[t[0]]

for i in range(1,N):
  Ruisekit.append(t[i]+Ruisekit[i-1])
  
print(Ruisekit)




downstart=[]

for i in range(N-1):
  if v[i]>v[i+1]:
    downstart.append(t[i]-(v[i]-v[i+1]))

print(downstart)

velocity=0
downindex=0

if downstart:
  nextdownstarttime=downstart[downindex]

state='up'
upstarttime=0
upstartspeed=0
answer=0
maxspeed=v[0]
maxspeedindex=0

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

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0

if n==1:
    if a[0]>=b[0]*2:
        print(b[0]**2+b[0]*(a[0]-b[0]*2))
    else:
        print(a[0]/2**2)
else:
    for i in range(n):
        if i==n-1:

Submission status: Runtime Error

Solution code:
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:])))

Submission status: Runtime Error

Solution code:
#076-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n=I()
t=IL()
v=IL()
c=[[0,0,0]]
for i in range(n):
    l=c[-1][0]
    r=l+t[i]
    v=v[i]
    c.append([l,r,v])
c.append([c[-1][1],c[-1][1],0])

def f(a):
    vmax=1000
    for l,r,v in c:
        t_vmax=0
        if a<=l:
            t_vmax=v+(l-a)
        elif l<a<=r:
            t_vmax=v
        else:
            t_vmax=v+(a-r)
        vmax=min(vmax,t_vmax)
    return vmax

d=0
vl=[]
tmax=c[-1][1]
for i in range(2*tmax+1):
    vmax=f(i/2)
    vl.append(vmax)

for i in range(2*tmax):
    d+=(vl[i]+vl[i+1])*0.5*0.5
print(d)

Submission status: Runtime Error

Solution code:
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)
v=lambda s:min(map(lambda x:x(s),o))

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

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

Submission status: Runtime Error

Solution code:

from collections import deque

def upperlimit(ts, vs):
    """
        return value f gives speed limit at time t
    """
    xs = [(-100, 0)]
    t = 0
    for s, v in zip(ts, vs):
        xs.append((t, v))
        t += s
    xs.append((t, 0))
    #print(xs)

    """xs has time of start, instead of end"""
    """ achieve, [)"""
    
    def limit(s):
        """ugh! slow"""
        previous = 0
        for t, v in xs:
            if s == t:
                return min(previous, v)
            if s < t:
                return previous
            else:
                previous = v
        return 0
    return limit, t


def foo(ts, vs):
    f, end = upperlimit(ts, vs)
    xs = deque()
    xs.append((0,0,0.0))

    visited = set()

    while True:
        t, v, r = xs.popleft()

        if (t, v) in visited:
            continue
        visited.add((t,v))
        limit = f(t/2) * 2
        if limit < v: 
            """over speeding"""
            previous_limit = f((t-1)/2)*2
            if previous_limit > limit:
                """rewind"""
                rewind = previous_limit - limit
                for i in range(rewind):
                    xs.popleft()
                for i in range(rewind):
                    p = (t - rewind + i + 1, previous_limit - i)
                    visited.add(p)
                    p = (t - rewind + i + 2, previous_limit - i)
                    visited.add(p)
            continue

        #print("%d, %d, %f"%(t, v, r))
        if t >= end * 2:
            """time up"""
            return r/4

        # deacc
        xs.appendleft((t+1, v-1, r+v-0.5))
        # keep
        xs.appendleft((t+1, v, r+v))
        # acc
        xs.appendleft((t+1, v+1, r+v+0.5))
    return 0




if __name__ =="__main__":
    n = int(input())
    ts = tuple(map(int, input().split()))
    vs = tuple(map(int, input().split()))

    print(foo(ts, vs))

Submission status: Runtime Error

Solution code:
n = int(raw_input())
times = map(int, raw_input().split())
speeds = map(int, raw_input().split())

print(times, speeds)

dst = 0
s = 0

for i in range(n):
    #loop over each section of time
    for j in range(times[i]):
        #j is in 100 1 sec intervals
        if (s < speeds[i]):
            s+= 1
            dst += s - 0.5
            print(s^2, dst,  "accelerating")
        elif (s > speeds[i]):
            s-= 1
            dst += s + 0.5
        else:
            dst += s

dst -= (s*s)/2
print(dst, s)

Submission status: Runtime Error

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

T = sum(t)

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

def vel(x):
	minv = f(0, 0, 0, x)
	minv = min(minv, f(T, T, 0, x))
	l = 0
	r = 0
	for i in range(len(t)):
		r += t[i]
		minv = min(minv, f(l, r, v[i], x))
		l += t[i]
	return minv

area = 0
velo = [0] * (2 * T + 1)
for i in range(2*T+1):
	velo[i] = vel(0.5*i)
for i in range(2*T):
	area += 0.25 * (vel[i] + vel[i+1])

print(area)

Submission status: Runtime Error

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

T = sum(t)

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

def vel(x):
	minv = f(0, 0, 0, x)
	minv = min(minv, f(T, T, 0, x))
	l = 0
	r = 0
	for i in range(len(t)):
		r += t[i]
		minv = min(minv, f(l, r, v[i], x))
		l += t[i]
	return minv

area = 0
velo = [0] * (2 * T + 1)
for i in range(2*T+1):
	velo[i] = vel(0.5*i)
for i in range(2*T+1):
	area += 0.25 * (vel[i] + 2 * vel[i+1] + velo[i+2])

print(area)