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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from itertools import accumulate

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

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

ans += mn_f * 0.25

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from itertools import accumulate

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

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

v_li.append(0)

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

print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

        preh = height
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

INF = 1000

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

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

    preh = height
print(ans)

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [(i/2) if i<T/2 else ((T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i,ti in enumerate(t):
    te += ti*2
    vi = v[i]
    vt = [min(vtj,vi+((-(j-ts)/2) if j<ts else ((j-te)/2) if j>te else 0)) for j,vtj in enumerate(vt)]
    ts = te
print(sum(vt)/2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    vi = v[i]
    vt = [min(vtj,vi+((-(j-ts)/2) if j<ts else ((j-te)/2) if j>te else 0)) for j,vtj in enumerate(vt)]
    ts = te
print(sum(vt)/2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    vi = v[i]
    vt = [min(vtj,vi+max(0,-(j-ts)/2,(j-te)/2)) for j,vtj in enumerate(vt)]
    ts = te
print(sum(vt)/2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    vi = v[i]
    vt = [min(vt[j],vi+max(0,-(j-ts)/2,(j-te)/2)) for j in range(T+1)]
    ts = te
print(sum(vt)/2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    vi = v[i]
    for j in range(T+1):
        vt[j] = min(vt[j],vi+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    for j in range(T+1):
        vt[j] = min(vt[j],v[i]+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, T: "List[int]", V: "List[int]"):
    t_period = [0 for i in range(N+1)]
    for i in range(N):
        t_period[i+1] = t_period[i] + T[i]*2

    limit = [0 for t in range(t_period[N]+1)]
    for i in range(1, N):
        limit[t_period[i]] = min((V[i-1], V[i]))
    for i in range(N):
        limit[t_period[i]+1:t_period[i+1]] = [V[i]] * (t_period[i+1] - t_period[i] - 1)
    
    speed = [0 for t in range(t_period[N]+1)]

    for v in range(1, 201):
        for t in range(1, t_period[N]):
            speed[t] = min([limit[t], speed[t-1]+0.5, speed[t+1]+0.5])

    total = 0
    for t in range(t_period[N]):
        total += (speed[t] + speed[t+1]) * 0.5 * 0.5
    
    print(total)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    t = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    v = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, t, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def add_sentinel(t: list, v: list):
    t = [0] + [0] + t + [t[-1]]
    v = [0] + v + [0]
    return t,v
    
def find_max_vel(ti: int, v: list, intervals: list):
    ret = float('inf')
    for inti, interval in enumerate(intervals):
        st, ed = interval
        
        if ti < st:
            ret = min(ret, v[inti] + (st - ti))
        elif st <= ti <= ed:
            ret = min(ret, v[inti])
        else:
            ret = min(ret, v[inti] + (ti - ed))
            
    return ret

n = ni()
t = list(li())
v = list(li())

t,v = add_sentinel(t, v)
t = list(accumulate(t))
intervals = [(st, ed) for st, ed in zip(t[:-1], t[1:])]

vels = []
for ti in range(2*max(t)+1):
    timestamp = ti/2
    vels.append(find_max_vel(timestamp, v, intervals))
    
ans = 0
for left, right in zip(vels[:-1], vels[1:]):
    ans += (left + right) * 0.5 * 0.5
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
now=0
T=list(map(int,input().split()))
for i in range(1,N):
    T[i]+=T[i-1]
T=[-1*float('inf'),0]+T+[float('inf')]
V=list(map(int,input().split()))
V=[0]+V+[0]
vt=[float('inf')]*(2*T[-2]+1)
for t in range(len(vt)):
    now=t/2
    for k in range(N+2):
        if now<T[k]:
            vt[t]=min(vt[t],V[k]+T[k]-now)
        elif T[k]<=now<=T[k+1]:
            vt[t]=min(vt[t],V[k])
        elif T[k+1]<now:
            vt[t]=min(vt[t],V[k]+now-T[k+1])
ans=0
for i in range(len(vt)-1):
    ans+=0.25*(vt[i]+vt[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
now=0
T=[-1*float('inf'),0]
for t in map(int,input().split()):
    T.append(T[-1]+t)
T.append(float('inf'))
V=list(map(int,input().split()))
V=[0]+V+[0]
vt=[float('inf')]*(2*T[-2]+1)
for t in range(len(vt)):
    now=t/2
    for k in range(N+2):
        if now<T[k]:
            vt[t]=min(vt[t],V[k]+T[k]-now)
        elif T[k]<=now<=T[k+1]:
            vt[t]=min(vt[t],V[k])
        elif T[k+1]<now:
            vt[t]=min(vt[t],V[k]+now-T[k+1])
ans=0
for i in range(len(vt)-1):
    ans+=0.25*(vt[i]+vt[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def velsup(a,b,c,x):
    if a<=x<=b:
        return c
    elif x<a:
        return (a-x)+c
    else:
        return (x-b)+c

N=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=t[i]+S[i]
TT=S[N]
vt=[0 for i in range(2*TT+1)]
for tt in range(TT*2+1):
    ta=tt/2
    va=min(velsup(-1,0,0,ta),velsup(TT,TT+1,0,ta))
    for i in range(N):
        va=min(va,velsup(S[i],S[i+1],v[i],ta))
    vt[tt]=va
ans=0
for i in range(2*TT):
    ans+=(vt[i]+vt[i+1])*0.25
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]
lines.append((t,t+1,0))
def f(x):
    speed = 10**18
    for x1,x2,vv in lines:
        if x<x1:
            speed = min(speed,vv+x1-x)
        elif x>x2:
            speed = min(speed,vv+x-x2)
        else:
            speed = min(speed,vv)
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
for a in range(2*t):
    res += (dp[a]+dp[a+1])
print(res*0.25)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

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

lines.append((t,t+1,0))
def ff(p,x):
    x1,x2,vv = p
    if x<x1:
        return vv+x1-x
    elif x>x2:
        return vv+x-x2
    else:
        return vv
def f(x):
    speed = 10**18
    for line in lines:
        speed = min(speed,ff(line,x))
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
for a in range(2*t):
    res += 0.25*(dp[a]+dp[a+1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

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

lines.append((t,t+1,0))
def ff(p,x):
    x1,x2,vv = p
    if x<x1:
        return vv+x1-x
    elif x>x2:
        return vv+x-x2
    else:
        return vv
def f(x):
    speed = 10**18
    for line in lines:
        speed = min(speed,ff(line,x))
    return speed 
res = 0
for a in range(2*t):
    a = a/2
    res += 0.25*(f(a)+f(a+0.5))
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
v.insert(0, 0)
v.append(0)
l = [0, 0]
r = [0]
for i in range(n):
    l.append(l[i+1]+t[i])
    r.append(l[i+2])
r.append(r[n])
d = 0
vl = 0
for k in range(l[n+1]*2):
    now = k / 2 + 0.5
    vr = 1000
    for i in range(n+2):
        tv = 0
        if now < l[i]:
            tv = v[i] + l[i] - now
        elif now < r[i]:
            tv = v[i]
        else:
            tv = v[i] + now - r[i]
        vr = min(vr, tv)
    d += (vl+vr) * 0.25
    vl = vr
print(d)

Submission status: Time Limit Exceeded

Solution code:

N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
# 解説読んだ後
def get_maxspeed(left,right,vmax):
    def maxspeed(t):
        if t<=left:
            return vmax+(left-t)
        elif left< t < right:
            return vmax
        else:
            return vmax+t-right
    return maxspeed
funcs=[]
funcs.append(get_maxspeed(0,0,0))
left=0
for i in range(N):
    funcs.append(get_maxspeed(left,left+T[i],V[i]))
    left+=T[i]
funcs.append(get_maxspeed(left,left,0))
dist=0.0
speed=0
t=0
while t<=left:
    speed2=min(fc(t) for fc in funcs)
    if 0< t:
        dist+=(speed+speed2)*0.5/2
    speed=speed2
    t+=0.5
print(dist)

Submission status: Time Limit Exceeded

Solution code:
N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
# 解説読んだ後
def maxspeed(left,right,t,vmax):
    if t<=left:
        return vmax+(left-t)
    elif left< t < right:
        return vmax
    else:
        return vmax+t-right
funcs=[]
funcs.append((0,0,0))
left=0
for i in range(N):
    funcs.append((left,left+T[i],V[i]))
    left+=T[i]
funcs.append((left,left,0))
dist=0.0
speed=0
t=0
while t<=left:
    speed2=min(maxspeed(pm[0],pm[1],t,pm[2]) for pm in funcs)
    if 0< t:
        dist+=(speed+speed2)*0.5/2
    speed=speed2
    t+=0.5
print(dist)

Submission status: Time Limit Exceeded

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

b = 2
bg = 1.0 / b

M = [] #t = i秒の最高速度
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
    while le >= 0 :
        M[le] = min(M[le], V[i] + j*bg)
        #print(M[le])
        j += 1
        le -= 1
    j = 0
    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)

Submission status: Time Limit Exceeded

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

M = [] #t = i秒の最高速度
for i in range(n) :
    for j in range(T[i] * 10) :
        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] * 10
    ri = R[i+1] * 10

    
    j = 0
    while le >= 0 :
        M[le] = min(M[le], V[i] + j*0.1)
        #print(M[le])
        j += 1
        le -= 1
    j = 0
    while ri < len(M) :
        M[ri] = min(M[ri], V[i] + j*0.1)
        j += 1
        ri += 1

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

M += [0]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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
    for t2 in range(0, t0 * 2):
        sptmp[t2] += t0 - t2 * 0.5
    for t2 in range(t1 * 2, t2_max + 1):
        sptmp[t2] += t2 * 0.5 - t1
    speeds = np.minimum(speeds, sptmp)

ans = sum(speeds) / 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
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 = list(accumulate(T))
INF = 10 ** 9

t2_max = accT[-1] * 2
speeds = [INF] * (t2_max + 1)
for t0, t1, v in zip(accT[:-1], accT[1:], V):
    for t2 in range(0, t0 * 2):
        speeds[t2] = min(speeds[t2], (t0 - t2 * 0.5) + v)
    for t2 in range(t0 * 2, t1 * 2):
        speeds[t2] = min(speeds[t2], v)
    for t2 in range(t1 * 2, t2_max + 1):
        speeds[t2] = min(speeds[t2], (t2 * 0.5 - t1) + v)

ans = sum(speeds) / 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
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 = list(accumulate(T))
INF = 10 ** 9

def speed(t, t0, t1, v):
    if t < t0:
        return (t0 - t) + v
    elif t > t1:
        return (t - t1) + v
    return v

ans = 0
sp_pre = 0
for t2 in range(0, accT[-1] * 2 + 1):
    t = t2 * 0.5
    sp = INF
    for t0, t1, v in zip(accT[:-1], accT[1:], V):
        sp = min(sp, speed(t, t0, t1, v))
    ans += 0.25 * (sp + sp_pre)
    sp_pre = sp

print(ans)

Submission status: Time Limit Exceeded

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][1]
    r=l+t[i]
    c.append([l,r,v[i]])
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: Time Limit Exceeded

Solution code:
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
                max_velocity[i+1]=max_velocity[i+1]-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)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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)]  # 0.5刻みで×２

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)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
tl = list(map(int, input().split()))
vl = list(map(int, input().split()))
T = sum(tl)

conditions = []
t = 0
conditions.append((t,t,0))
for i in range(n):
    conditions.append((t,t+tl[i],vl[i]))
    t += tl[i]
conditions.append((t,t,0))

def calc_v(t):
    maxv = 1000
    for (lt,rt,v) in conditions:
        if t<=lt:
            maxv = min(maxv, v+(lt-t))
        elif lt<t<rt:
            maxv = min(maxv, v)
        else:
            maxv = min(maxv, v+(t-rt))
    return maxv

res = 0
for i in range(2*T):
    t = i*0.5
    res += (calc_v(t)+calc_v(t+0.5))*0.5/2.0

print(res)

Submission status: Time Limit Exceeded

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

minV = [float("inf") for i in range(2*L[-1] + 1)]
for i in range(2*L[-1]+1):
    for j in range(N):
        minV[i] =min(minV[i], VM(i*0.5, j))
    minV[i] = min(minV[i], i*0.5, L[-1] - i*0.5)

Ans = 0
for i in range(2*L[-1]):
    Ans += (minV[i] + minV[i+1])/4
print(Ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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