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())
T = [0] + list(map(int,input().split()))
V = [-1] + list(map(int,input().split()))

ans = 0
for i in range(1,N+1):
    T[i] += T[i-1]
time = T[-1]
upper  = {}

state = N
speed = 0

for t in range(2*time,0,-1):
    t *= 0.5
    if T[state-1] == t:
        speed = min(V[state],speed)
        state -= 1
    upper[t] = min(speed,V[state])
    speed += 0.5

speed = 0
pre = -1
Ans = []
for t in range(1,2*time+1):
    t = t*0.5
    speed += 0.5
    speed = min(speed,upper[t])
    Ans.append(speed)
    if pre == speed:
        ans += 0.5*speed
    elif pre > speed:
        ans += 0.5*speed + 0.125
    else:
        ans += 0.5*speed - 0.125
    pre = speed
print(ans)

Submission status: Accepted

Solution code:
def f(v,t,now):
    res = now
    s = 0
    for i in range(len(t)-1):
        s+=t[i]
        if s-t[i]>=now:
            res = min(res,v[i]+s-t[i]-now)
        elif s>=now>=s-t[i]:
            res = min(res,v[i])
        else:
            res = min(res,v[i]+now-s)
    res = min(res, s-now)
    return max(res,0)
n = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
t.append(0)
v.append(0)
ans = []
for i in range(sum(t)+1):
    ans.append(f(v,t,i))
    ans.append(f(v, t, i+0.5))
r = 0
for i in range(len(ans)-1):
    r+=(ans[i]+ans[i+1])/4
print(r)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

L=[0]
for i in range(N):
    a=[v[i] for j in range(t[i]*2)]
    #print(a)
    L+=a
X=[]
for i in range(1,len(L)):
    if L[i-1]>L[i]:
        X.append(i)
for i in X:
    L[i-1]=L[i]
L[-1]=0

S=copy.deepcopy(L)
#E=copy.deepcopy(L)
#print(L)
for i in range(1,len(L)):
    if L[i-1]<L[i]:
        for j in range(10**5):
            if S[i-1]+0.5*j>400 or (i-1+j)>(len(L)-1):
                break
            else:
                S[i-1+j]=min(S[i-1]+0.5*j,S[i-1+j])
    elif L[i-1]>L[i]:
        for j in range(10**5):
            if S[i]+0.5*j>400 or i<j:
                break
            else:
                S[i-j]=min(S[i]+0.5*j,S[i-j])
#print(S)
ans=0
for i in range(1,len(S)):
    ans+=(S[i-1]+S[i])/2
print(ans/2)

Submission status: Accepted

Solution code:
N=int(input())
inl=list(map(lambda x: int(x)*2,input().split()))
vs=list(map(int,input().split()))

sumtime = sum(inl)

limits = [0]
for i, t in enumerate(inl):
    for _ in range(t):
        limits.append(vs[i])

resv = [0]
for i in range(1, sumtime+1):
    resv.append(min(resv[-1]+0.5, limits[i]))

resv[sumtime] = 0
for i in reversed(range(1, sumtime+1)):
    resv[i-1] = min(resv[i]+0.5, resv[i-1], limits[i])

# print(limits)
# print(resv)
res = 0.0
for i in range(sumtime):
    res += (resv[i] + resv[i+1])*0.5

print(res*0.5)

Submission status: Accepted

Solution code:
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
def exe(x, y, z, t):
  ans = t * y
  if x < y:
    ans -= (y - x) * (y - x) / 2
  if y > z:
    ans -= (y - z) * (y - z) / 2
  return ans

def upd(x, y, z, t):
  a = y - x
  b = y - z
  if y > z:
    if t < a:
      y = x + t
    elif t < a + b:
      y = x + (t + (z - x)) / 2
  else:
    if t < a:
      y = x + t
  return y

v = [0] + v + [0]
L = [0] * len(v)
v[1] = upd(v[0], v[1], v[2], t[0])
v[-2] = upd(v[-1], v[-2], v[-3], t[-1])
for i in range(1, N):
  k = -1
  for j in range(1, N + 1):
    if L[j] == 0:
      if k == -1:
        k = j
      else:
        if v[j] < v[k]:
          k = j
  L[k] = 1
  if k != 1:
    v[k - 1] = upd(min(v[k], v[k - 2]), v[k - 1], max(v[k], v[k - 2]), t[k - 2])
  if k != N:
    v[k + 1] = upd(min(v[k], v[k + 2]), v[k + 1], max(v[k], v[k + 2]), t[k])

ans = 0
for i in range(N):
  ans += exe(v[i], v[i + 1], v[i + 2], t[i])

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

tl = []
v1 = [0]+v+[0]
ts = 0
for i in range(N+1):
    tl.append([ts,min(v1[i],v1[i+1])])
    if i!=N:
        ts+=t[i]

max_v = []

k = 0
for i in range(2*ts+1):
    mv = 10**27
    if tl[k+1][0]<i/2:
        k+=1
    for j in range(len(tl)):
        mv = min(mv,abs(i/2-tl[j][0])+tl[j][1],v[k])
    max_v.append(mv)
s = 0
for i in range(2*ts):
    s+=max_v[i]+max_v[i+1]

print(s/4)

Submission status: Accepted

Solution code:

def main():
    buf = input()
    N = int(buf)
    buf = input()
    buflist = buf.split()
    t = list(map(int, buflist))
    buf = input()
    buflist = buf.split()
    v = list(map(int, buflist))
    t.append(0)
    v.append(0)
    for i, _ in enumerate(t): # double time and speed to make calculation easier
        t[i] *= 2
        v[i] *= 2
    time = 0
    last_speed = 0
    speed = 0
    distance = 0.0
    point = 0
    spd_time_list = []
    for i, _ in enumerate(t):
        spd_time_list.append((v[i], (0 if not spd_time_list else t[i-1] + spd_time_list[-1][1])))
    while time < spd_time_list[-1][1]:
        last_speed = speed
        brake = False
        for i in range(point+1, len(spd_time_list)):
            if speed >= spd_time_list[i][0] + (spd_time_list[i][1] - time):
                brake = True
                break
        if brake:
            speed -= 1
        elif speed < spd_time_list[point][0]:
            speed += 1
        distance += (last_speed + speed) / 2
        time += 1
        if time >= spd_time_list[point+1][1]:
            point += 1
    distance /= 4 # roll back time and speed (and so the distance)
    print(distance)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
S=sum(T)
v=[0]*(sum(T)*2+1)
def f(x,l,r,vmax):
    if x<l:
        return vmax+(l-x)
    elif l<=x<=r:
        return vmax
    else:
        return vmax+(x-r)
for i in range(S*2+1):
    l=0
    r=0
    v[i]=f(i*0.5,l,r,0)
    for j in range(N):
        r+=T[j]
        v[i]=min(v[i],f(i*0.5,l,r,V[j]))
        l=r

    v[i]=min(v[i],f(i*0.5,l,r,0))
ans=0
for i in range(S*2):
    ans+=(v[i+1]+v[i])*0.25
print(ans)

Submission status: Accepted

Solution code:
N = int(raw_input())
ts = map(int, raw_input().split(" "))
vs = map(int, raw_input().split(" "))
tsa = [0]
for t in ts:
    tsa.append(tsa[-1]+t)

T = 0
X = 0
V = 0
def acc():
    ppp = False
    for j in range(N):
        if tsa[j] <= T:
            continue
        if vs[j] > V:
            continue
        c = tsa[j] - T - (V - vs[j])
        if c <= 0:
            return -1
        d = tsa[j] - (T+1) - (V+1 - vs[j])
        if d < 0:
            ppp = True
    if tsa[-1] - T - (V - 0)<=0:
        return -1
    if tsa[-1] - (T+1) - (V+1 - 0) < 0:
        ppp = True
    if ppp:
        return 0
    return 1

def tind():
    for i in range(len(ts)):
        if tsa[i] <= T and  T < tsa[i+1]:
            return i

for i in range(sum(ts)):
    a = acc()
    ti  = tind()
    if a == 1:
        if V == vs[ti]:
            X += V
        else:
            X += V + 0.5
            V += 1
    elif a == 0:
        if V == vs[ti]:
            X += V
        else:
            X += V + 0.25
    else:
        X += V - 0.5
        V -= 1
    T=i+1

print X

Submission status: Accepted

Solution code:
N = int(input())
t = [0] + [int(x) for x in input().split()]
v = [0] + [int(x) for x in 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[i] = min(start + t[i+1], v[i], v[i+1])

speed = [min(x,y) for x,y in zip(max_speed_from_left,max_speed_from_right)]

def dist(left_speed,right_speed,t,v):
  x = (v - left_speed) + (v - right_speed)
  if x >= t:
    v = (left_speed + right_speed + t)/2
    x = t
  # 最高速度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

answer = 0
for i in range(1,N+1):
  answer += dist(speed[i-1],speed[i],t[i],v[i])
print(answer)

Submission status: Accepted

Solution code:
N=int(input())
t=list(map(int, input().split()))
v=list(map(int, input().split()))
T=sum(t)
V=[0]*(T+2)
from collections import deque
q=[deque() for i in range(101)]
s=0
for i in range(N):
    temp=min(V[s],v[i])
    q[temp].append(s)
    for j in range(t[i]):
        V[s+j+1]=v[i]
    s+=t[i]
q[0].append(T)
vans=[-1]*(T+1)
for i in range(101):
    while(len(q[i])>0):
        s=q[i].popleft()
        if vans[s]==-1:
            vans[s]=i
        if s>0 and vans[s-1]==-1:
            if V[s]>i:
                q[i+1].append(s-1)
            else:
                q[i].append(s-1)
        if s<T and vans[s+1]==-1:
            if V[s+1]>i:
                q[i+1].append(s+1)
            else:
                q[i].append(s+1)
ans=0
for i in range(T):
    if vans[i+1]>vans[i]:
        ans+=vans[i]+0.5
    elif vans[i+1]<vans[i]:
        ans+=vans[i+1]+0.5
    elif V[i+1]>vans[i]:
        ans+=vans[i]+0.25
    else:
        ans+=vans[i]
print(ans)

Submission status: Accepted

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

T = np.array(T).cumsum()
V = np.array(V)

va = []
i = 0
for t in np.arange(0, T[-1], 0.5):  # 0.5 区切りの時間
    if t < T[i]:
        va.append(V[i])
    else:
        i += 1
        va.append(min(V[i], V[i - 1]))
va.append(0)

v = 0
for i in range(len(va)):
    va[i] = min(va[i], v)
    v = va[i] + 0.5
v = 0
for i in reversed(range(len(va))):
    va[i] = min(va[i], v)
    v = va[i] + 0.5

print((np.array(va) / 2).sum())

Submission status: Accepted

Solution code:
N = int(input())

tli = [ int(it)*2 for it in input().split() ]
vli = [ int(it)*2 for it in input().split() ]

vmax = [0]
for i in range(len(tli)):
  tmp = vmax.pop()
  vmax.append( min(tmp,vli[i]) )
  vmax.extend( [vli[i]]*(tli[i]) )
vmax[-1]=(0)
vmax[0]=0
T = len( vmax ) - 1

for j in range( 1000 ):
  for i in range( T ):
    vmax[i+1] = min( vmax[i]+1 , vmax[i+1] )
  for i in range( T,0,-1):
    vmax[i-1] = min( vmax[i]+1 , vmax[i-1] )
  if (j==0):
    pass
    #print ( vmax )
    
print ( 0.25 * sum(vmax) )

Submission status: Accepted

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

cumsum_t = [0]*(n+1)
for i in range(n):
    cumsum_t[i+1] = cumsum_t[i] + t[i]

v_max = [0]*(2*sum(t) + 1)
for i in range(len(cumsum_t) - 1):
    for j in range(2*cumsum_t[i], 2*cumsum_t[i+1]):
        v_max[j] = v[i]
for i in range(len(cumsum_t) - 1):
    v_max[cumsum_t[i+1]*2] = min(v_max[cumsum_t[i+1]*2], v[i])

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

print(sum(speed)/2)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
kukan = [(0,0,0)]
for i in range(n):
    kukan.append((kukan[i][1],kukan[i][1]+t[i]*2,v[i]))
kukan.append((T,T,0))
vt = [[1000]*(len(kukan)) for _ in range(T+1)]
k = 0
for ts,te,v_ in kukan:
    for i in range(ts,te+1):
        vt[i][k] = v_
    for i in range(ts-1,-1,-1):
        vt[i][k] = vt[i+1][k]+0.5
    for i in range(te+1,T+1):
        vt[i][k] = vt[i-1][k]+0.5
    k += 1
ans = 0
d = [0]*len(vt)
for i in range(len(vt)):
    d[i] = min(vt[i])
for i in range(1,len(vt)):
    ans += (d[i]+d[i-1])*0.25
print(ans)

Submission status: Accepted

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

maxv = [0]
for _t, _v in zip(t, v):
  maxv[-1] = min(maxv[-1], _v)
  for ti in range(_t * 2):
    maxv.append(_v)

N = len(maxv)
candv = [0] * N
for i in range(N - 1):
  candv[i + 1] = min(candv[i] + 0.5, maxv[i + 1])

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

ans = 0
for x1, x2 in zip(candv, candv[1:]):
  ans += (x1 + x2) * 0.5 / 2

print(ans)

Submission status: Accepted

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,ti in enumerate(t):
    te += ti*2
    vi = v[i]
    for j in range(ts,te):
        vt[j] = min(vt[j],vi)
    for j in range(te,T):
        if vt[j] >= (j-te)/2 + vi:
            vt[j] = (j-te)/2 + vi
        else:
            break
    for j in range(ts-1,-1,-1):
        if vt[j] >= -(j-ts)/2 + vi:
            vt[j] = -(j-ts)/2 + vi
        else:
            break
    ts = te
print(sum(vt)/2)

Submission status: Accepted

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]
    for j in range(ts,te):
        vt[j] = min(vt[j],vi)
    for j in range(te,T):
        if vt[j] >= (j-te)/2 + vi:
            vt[j] = (j-te)/2 + vi
        else:
            break
    for j in range(ts-1,-1,-1):
        if vt[j] >= -(j-ts)/2 + vi:
            vt[j] = -(j-ts)/2 + vi
        else:
            break
    ts = te
print(sum(vt)/2)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    t = f()
    v = f()
    


    sumt = sum(t)*2
    vs = [100000000] * (sumt+1)

    vs[0] = 0

    for i in range(1,sumt):
        totalt = 0
        idx = 0
        for k in range(n):
            totalt += t[k]*2
            if totalt >= i:
                idx = k
                break

        vs[i] = min(vs[i-1]+0.5, v[idx])

    vs[sumt] = 0
    for i in range(sumt-1, 0, -1):
        totalt = 0
        idx = 0
        for k in range(n):
            totalt += t[k]*2
            if totalt >= i+1:
                idx = k
                break

        vs[i] = min(vs[i+1]+0.5, vs[i], v[idx])

    ans = 0
    for i in range(sumt):
        ans += (vs[i]+ vs[i+1])/4


    # print(dict(zip(range(len(vs)), vs)))
    print(ans)

solve()

Submission status: Accepted

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


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

    V = [0] + V + [0]
    limit = np.zeros((N+2,t_period[N]+1))
    line = np.arange(0, t_period[N]/2+0.5, 0.5)
    for i in range(N+2):
        if i == 0:
            l, r = 0, 0
        elif i == N+1:
            l, r = t_period[N], t_period[N]
        else:
            l, r = t_period[i-1], t_period[i]
        limit[i] = np.max([-line + l * 0.5, line * 0, line - r * 0.5], axis=0) + V[i]
    speed = np.min(limit, axis=0)

    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: Accepted

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


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 = np.zeros((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]
    
    speed = np.zeros((t_period[N]+1,))

    for v in range(1, 201):
        speed[v:t_period[N]+1-v] = np.min(
            [limit[v:t_period[N]+1-v], speed[v-1:t_period[N]-v]+0.5, speed[v+1:t_period[N]+2-v]+0.5],
            axis=0
            )

    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: Accepted

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


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 = np.zeros((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]
    
    speed = np.zeros((t_period[N]+1,))

    for v in range(1, 201):
        speed[1:t_period[N]] = np.min([limit[1:t_period[N]], speed[0:t_period[N]-1]+0.5, speed[2:t_period[N]+1]+0.5], axis=0)

    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: Accepted

Solution code:
import numpy as np
 
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))

MAX_V=[0]
for t,v in zip(T,V):
  MAX_V[-1]=min(MAX_V[-1],v)
  for _ in range(t*2):
    MAX_V.append(v)
  #print(MAX_V)
  #print(len(MAX_V))

timelistsize=len(MAX_V)
REAL_V=[0]*timelistsize

#スピードが加速する部分の速度を表現
for i in range(1,timelistsize):
  REAL_V[i]=min(REAL_V[i-1]+0.5,MAX_V[i])

#終了位置から同じようにして減速部分の速度を表現
REAL_V[-1]=0
for i in range(timelistsize-1,0,-1):
  REAL_V[i-1]=min(REAL_V[i]+0.5,REAL_V[i-1])


#0.5秒刻みの速度ができているので、0.5を高さ,0.5秒ごとの速度を上辺,下辺とした台形面積を足す
answer=0
for i in range(timelistsize-1):
  answer+=((REAL_V[i]+REAL_V[i+1])*0.5/2)
print(answer)

'''
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: Accepted

Solution code:
def f(x,l,r,v):
    if 0<=x<=l:
        return v+(l-x)
    if l<=x<=r:
        return v
    if r<=x:
        return v+x-r
def speed(t):
    num=10**9
    for l,r,v in table:
        num=min(num,f(t,l,r,v))
    return num
N=int(input())
T=[int(i) for i in input().split()]
V=[int(i) for i in input().split()]
X=[0]*(N+1)
for i in range(1,N+1):
    X[i]=X[i-1]+T[i-1]
table=[(X[i] , X[i+1],V[i]) for i in range(N)]
table.append((0,0,0))
table.append((X[-1],X[-1],0))
#print(table)
s=speed(0)
meter=0
for i in range(1,2*X[-1]+1):
    t=speed(i*0.5)
    meter+=(s+t)*(0.25)
    s=t
print(meter)

Submission status: Accepted

Solution code:
# 19/4/17再戦
# -x + a = x + b だと x = (sum)/2で~.5になる可能性がある
# う～～～ん

n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
sum_t = sum(ts)
n = 2*sum_t+1
max_v = [float("inf")]*n
# 0から右上、-1から左上
for i in range(n):
    max_v[i] = min(i/2, (sum_t-i/2))

# intでtimeは管理するか...
# 0→0, 0.5→1, 1→2 ... i/2→i
t_cnt = 0
for t, v in zip(ts, vs):
    for j in range(2*t+1):
        max_v[t_cnt + j] = min(max_v[t_cnt + j], v)

    # 左側に伸ばしていく
    left = t_cnt
    while left >= 0:
        v_left = v + (t_cnt - left)/2
        if max_v[left] < v_left:
            break
        max_v[left] = v_left
        left -= 1
    # 右側に伸ばしていく
    t_cnt += 2*t
    right = t_cnt
    while right < n:
        v_right = v + (right - t_cnt)/2
        if max_v[right] < v_right:
            break
        max_v[right] = v_right
        right += 1

#print(max_v)
ans = sum(max_v) - (max_v[0]+max_v[-1])/2
print(ans/2)

Submission status: Accepted

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


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


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

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


ans = 0
for i in range(N - 1):
    x1, x2 = Feasible_V[i], Feasible_V[i + 1]
    ans += (x1 + x2) * 0.5 / 2

print(ans)

Submission status: Accepted

Solution code:
#    60 50
#    34 38

#  0  1   2  3   i
#  0  0  60 110  left 
#  0 60 110 110  right
#  0 34  38  0   speed
inf=1<<60
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
csum=0
left=[0]*(N+2)
right=[0]*(N+2)
for i in range(N):
    csum+=T[i]
    left[i+2]=csum
    right[i+1]=csum
right[N+1]=right[N]
speed=[0]+V+[0]

def calc(idx):
    l=inf
    r=inf
    for i in range(0,idx):
        #print(idx,i)
        #print(left)
        #print(right)
        l=min(l,speed[i]+(left[idx]-right[i]))
        r=min(r,speed[i]+(right[idx]-right[i]))
    for i in range(idx+1,N+2):
        l=min(l,speed[i]+(left[i]-left[idx]))
        r=min(r,speed[i]+(left[i]-right[idx]))
    l=min(l,speed[idx])
    r=min(r,speed[idx])
    width=right[idx]-left[idx]
    d=0
    #print(idx,width,l,r,speed[idx])
    if (speed[idx]-l)+(speed[idx]-r)<=width:
        d+=(speed[idx]+l)*(speed[idx]-l)/2
        d+=(speed[idx]+r)*(speed[idx]-r)/2
        d+=(speed[idx])*(width-(speed[idx]-l)-(speed[idx]-r))
    elif l<r:
        d+=(l+r)*(r-l)/2
        d+=(width-(r-l))*(r+r+(width-(r-l))/2)/2
    else:
        d+=(l+r)*(l-r)/2
        d+=(width-(l-r))*(l+l+(width-(l-r))/2)/2
    return d

ans=0
for i in range(1,N+1):
    ans+=calc(i)
print(ans)

Submission status: Accepted

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

m = [0]*(n+1)
z = [0]*(n+1)
for i in range(n-1,0,-1):
    m[i] = min(v[i], v[i-1], t[i] + m[i+1])
for i in range(1,n):
    z[i] = min(m[i], z[i-1]+t[i-1])

def dist(i):
    lspeed = z[i]
    rspeed = z[i+1]
    ta = v[i] - lspeed
    tb = v[i] - rspeed
    if ta + tb <= t[i]: # 山を押さえた形
        c = (lspeed+v[i])*ta/2 + v[i]*(t[i]-ta-tb) + (rspeed+v[i])*tb/2
    else: #山の形
        a = (rspeed+t[i]-lspeed)/2
        c = (2*lspeed+a)*a/2 + (lspeed+a+rspeed)*(t[i]-a)/2
    return c

ans=0
for i in range(0,n):
    ans += dist(i)

print(ans)

Submission status: Accepted

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

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

def dist(i,first): # distance,lastspeed
    ta = v[i] - first
    tb = v[i] - maxspeed[i+1]
    if ta + tb <= t[i]:
        c = (first+v[i])*ta/2 + v[i]*(t[i]-ta-tb) + (maxspeed[i+1]+v[i])*tb/2
        lastspeed = maxspeed[i+1]
    elif maxspeed[i+1] - first > t[i]:
        c = (first + first + t[i])*t[i]/2
        lastspeed = first + t[i]
    else:
        a = (maxspeed[i+1]+t[i]-first)/2
        c = (first+first+a)*a/2 + (first+a+maxspeed[i+1])*(t[i]-a)/2
        lastspeed = maxspeed[i+1]
    return c, lastspeed


ans = 0
firstspeed = 0
for i in range(n):
    d,firstspeed = dist(i,firstspeed)
    ans += d

print(ans)

Submission status: Accepted

Solution code:

import sys, collections, bisect, math, itertools
from fractions import gcd 
input = sys.stdin.readline #文字列入力のときは注意

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

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

#print(t)
#print(v)
#print(maxspeed)

def dist(first,i): # distance,lastspeed
    ti = t[i]
    vi = v[i]
    mi1= maxspeed[i+1]
    ta = vi - first
    tb = vi - mi1
    if ta + tb <= ti:
        c = (first+vi)*ta/2 + vi*(ti-ta-tb) + (mi1+vi)*tb/2
        lastspeed = mi1
    elif mi1 - first > ti:
        c = (first + first + ti)*ti/2
        lastspeed = first + ti
    else:
        a = (mi1+ti-first)/2
        c = (first+first+a)*a/2 + (first+a+mi1)*(ti-a)/2
#        print(a,'a',c,first,(first+first+a)*a/2, (first+a+mi1)*(ti-a)/2)
        lastspeed = mi1
#    print(c)

    return c, lastspeed


ans = 0
firstspeed = 0
for i in range(n):
    d,firstspeed = dist(firstspeed,i)
#    print(d,firstspeed)
    ans += d

print(ans)