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:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
t = LI()
v = LI()
T = sum(t)*2
vcandi =[[0]*(N+2) for _ in range(T+1)]
sumt = int(0)
for i in range(N):
    time = t[i]*2
    for j in range(sumt):
        vcandi[j][i] = v[i]+(sumt-j)*0.5
    for j in range(time+1):
        vcandi[sumt+j][i] = v[i]
    sumt = sumt+time
    for j in range(T-sumt+1):
        vcandi[sumt+j][i] = v[i]+j*0.5
for i in range(T+1):
    vcandi[i][N] = i*0.5
    vcandi[i][N+1] = (T-i)*0.5
ansV =[0]*(T+1)
for i in range(T+1):
    ansV[i] = min(vcandi[i])

#print(ansV)
cur = float(0)
for i in range(T):
    cur += (ansV[i]+ansV[i+1])/2*0.5

ans = cur
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))+[0]
V=max(v)
dp=[[0]]+[[] for i in range(V)]
for i in range(0,n):
    a=t[i]
    b=v[i]
    c=v[i+1]
    h=[[] for j in range(V+1)]
    for j in range(V+1):
        l=V-j
        if dp[l]:
            if max(0,l-a)<=min(b,l+a):
                for k in range(max(0,l-a),min(b,c,l+a)+1):
                    if not h[k]:
                        h[k]=dp[l]+[k]
    dp=h
ans=0
for i in range(n):
    a=t[i]
    b=v[i]
    v1=dp[0][i]
    v2=dp[0][i+1]
    if v1==v2==b:
        ans+=a*b
    elif v1==b:
        ans+=a*b-(b-v2)**2/2
    elif v2==b:
        ans+=a*b-(b-v1)**2/2
    else:
        if 2*b-v1-v2<=a:
            ans+=a*b-(b-v2)**2/2-(b-v1)**2/2
        else:
            ans+=a*a/2+a*v1-(a+v1-v2)**2/4
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
list_t = list(map(int, input().split()))
list_v = list(map(int, input().split()))

list_v2 = [0 for i in range(n+1)]
list_t.append(0)
list_v.append(0)
for i in range(n-1)[::-1]:
  list_v2[i] = min(list_v[i], list_v[i+1], list_v2[i+1] + list_t[i+1])

dist = 0
v0 = 0
for i in range(n):
  t1 = min(list_v[i] - v0, (list_t[i] - (v0 - list_v2[i])) / 2, list_t[i])
  t2 = max(v0 + t1 - list_v2[i], 0)
  dist += (2*v0+t1)*t1/2 + (v0+t1)*(list_t[i]-t1-t2) + (2*(v0+t1)-t2)*t2/2
  v0 = v0 + t1 - t2
print(dist)

Submission status: Accepted

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

def main():
    N = int(input())
    t = list(map(lambda x: int(x) * 2, input().split()))
    v = list(map(float, input().split())) + [0]

    for i in range(1, N):
        t[i] += t[i-1]
    t += [t[-1]]
    vnow = [0.0] * (t[-1] + 1)
    vr = [0.0] * (t[-1] + 1)
    r = 0
    for i in range(1, len(vr)):
        if i < t[r]:
            vr[i] = v[r]
        elif i == t[r]:
            vr[i] = min(v[r], v[r+1])
            r += 1
        vnow[i] = min(vnow[i-1] + 0.5, vr[i])
    for i in range(len(vr)-2, -1, -1):
        vnow[i] = min(vnow[i], vnow[i+1] + 0.5)
    
    print(sum(vnow) / 2)

if __name__ == "__main__":
    main()

Submission status: Accepted

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


V = [100] * (2*sum(t) + 1)
T = 0
for i in range(N):
    for j in range(T+1, T+t[i]*2+1):
        V[j] = min(V[j], v[i])
    T += t[i]*2

for i in range(min(len(V), 201)):
    V[i] = min(V[i], i*0.5)
for i in range(min(len(V), 201)):
    V[-i-1] = min(V[-i-1], i*0.5)
V
T = 0
for i in range(N-1):
    T += t[i]*2
    vi = min(V[T], v[i], v[i+1])
    for j in range(201):
        if T-j >= 0:
            V[T-j] = min(V[T-j], vi+0.5*j)
        if T+j <= len(V)-1:
            V[T+j] = min(V[T+j], vi+0.5*j)

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

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
x=[0]
for i in range(n):x+=[v[i]]*t[i]*2
x+=[0]
l=[min(x[i],x[i+1])for i in range(len(x)-1)]
for i in range(1,len(l)):l[i]=min(l[i],l[i-1]+0.5)
for i in range(len(l)-2,-1,-1):l[i]=min(l[i],l[i+1]+0.5)
print(sum(0.25*(l[i]+l[i-1])for i in range(1,len(l))))

Submission status: Accepted

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

st = [0]
s = 0
for i in range(N):
    s+=t[i]
    st.append(s)

T = st[N]
i = 0
max_v = [0]
while i<=T:
    mv = 10**28
    for j in range(N):
        if i<st[j]:
            mv = min(v[j]+st[j]-i,mv)
        elif i>st[j+1]:
            mv = min(v[j]+i-st[j+1],mv)
        else:
            mv = min(v[j],mv)
    mv = min(T-i,i,mv)
    max_v.append(mv)
    i+=0.5

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
tlist = list(map(int, input().split()))
vlist = list(map(int, input().split()))
vlist.append(0)
flag = True
while flag:
    flag =  False
    for i in range(N):
        if vlist[i]-vlist[i+1] > tlist[i]:
            vlist[i] = vlist[i+1]+tlist[i]
            flag = True
speed = 0
x = 0
for i in range(N):
    ti = tlist[i]
    vi = vlist[i]
    vj = vlist[i+1]
    if vi <= vj:
        if vi-speed <= ti:
            x += ti*vi - ((vi-speed)**2)/2
            speed = vi
        else:
            x += ti*(speed+ti) - (ti**2)/2
            speed += ti
    else:
        if speed+ti <= vj:
            x += ti*(speed+ti) - (ti**2)/2
            speed += ti
        elif 2*vi-speed-vj <= ti:
            x += ti*vi - ((vi-speed)**2)/2 - ((vi-vj)**2)/2
            speed = vj
        else:
            a = (ti+vj-speed)/2
            x += a*(2*speed+a)/2 + (ti-a)*(2*vj+ti-a)/2
            speed = vj
print(x)

Submission status: Accepted

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

Tsum = sum(T)
keika = []
tmp = 0
for i in range(N):
    keika.append([tmp,tmp+T[i]])
    tmp += T[i]

G = [[0]*(N+1) for i in range(2*Tsum+1)]

for i in range(2*Tsum+1):
    G[i][0] = min(i/2,Tsum-i/2)
for i in range(N):
    t0,t1 = keika[i]
    for j in range(2*t0):
        G[j][i+1] = V[i] + t0 - j/2
    for j in range(2*t0,2*t1+1):
        G[j][i+1] = V[i]
    for j in range(2*t1+1,2*Tsum+1):
        G[j][i+1] = V[i] + j/2 - t1

ans = 0
for i in range(2*Tsum):
    v0 = min(G[i])
    v1 = min(G[i+1])
    ans += (v0+v1)/4
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
T = [0]*(N+1)
for i in range(N):
    T[i+1] = T[i]+t[i]
def f(i, t):
    
    if T[i]<=t<=T[i+1]:
        return v[i]
    if t<T[i]:
        return v[i]+(T[i]-t)
    else:
        return v[i]+(t-T[i+1])
limit = [0]*(T[-1]*2+1)
for t in range(1, T[-1]*2+1):
    limit[t] = min(min(f(i, t/2) for i in range(N)), t/2, T[-1]-t/2)
print(sum(limit)/2)

Submission status: Accepted

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

tmax = sum(T)
Vmax = max(V)
dp = [[-1 * float('inf') for _ in range(Vmax + 1)] for _ in range(tmax)]
dp[0][0] = 0
i = 0
j = 0
vmax = V[0]
for t in range(1, tmax):
    i += 1
    if i == T[j] + 1:
        i = 1
        j += 1
        vmax = V[j]
    for v in range(1, vmax + 1):
        acc = dp[t - 1][v - 1] + v - 0.5 if v != 0 else 0.5
        if v < vmax:
            same = dp[t - 1][v] + v + 0.25
            bra = dp[t - 1][v + 1] + v + 0.5
        else:
            same = dp[t - 1][v] + v
            bra = -float('inf')
        dp[t][v] = max(acc, same, bra)

if tmax == 1:
    print(0.25)
else:
    print(dp[-1][1] + 0.5)

Submission status: Accepted

Solution code:

N = int(input())

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

alltime = sum(t)
maxslis = []
rmaxslis = []



spd = 0
ans = 0

for i in range(N):

    for j in range(t[i]):
        maxslis.append(v[i])
        maxslis.append(v[i])
        rmaxslis.append(v[i])


maxslis.reverse()


for i in range(alltime * 2):

    if i == 0:
        able = 0.5
        maxslis[i] = 0

    elif able < maxslis[i]:
        maxslis[i] = able
        able += 0.5

    else:
        able = maxslis[i]

maxslis.reverse()
maxslis.append(0)

#print (maxslis)
dtflag = False

for i in range(alltime * 2 + 1):

    #print (i+1,maxslis[i],spd)

    if spd < maxslis[i]:

        ans += spd * 0.5 + 0.125
        spd += 0.5
        #if spd != maxslis[i]:
            #dtflag = True

    elif spd == maxslis[i]:

        #if dtflag and rmaxslis[i] != maxslis[i]:
            #ans += 0.25
            #print (i+1)
        ans += spd * 0.5
        dtflag = False

    else:
        ans += spd * 0.5 - 0.125
        spd -= 0.5
        dtflag = False

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

for i in range(1, N) :
        t[i] += t[i-1]
        
l = [t_ + v_ for t_, v_ in zip(t, v[1:]+[0])]
for i in range(N-2, -1, -1) :
    l[i] = min(l[i], l[i+1])
    
cur_v, cur_t = 0, 0
ret = 0
for i in range(N) :
    t1 = v[i] - cur_v + cur_t
    t2 = l[i] - v[i]
    if t[i] < t1 <= t2 :
        ret += (2 * cur_v + t[i] - cur_t) * (t[i] - cur_t) / 2
        cur_v = cur_v + t[i] - cur_t
        
    elif cur_t <= t1 <= t2 :
        ret += (t1 - cur_t) * (cur_v + v[i]) / 2
        if t2 <= t[i] :
            ret += (t2 - t1) * v[i]
            ret += (t[i] - t2) * (v[i] + l[i] - t[i]) / 2
            cur_v = l[i] - t[i]
        else :
            ret += (t[i] - t1) * v[i]
            cur_v = v[i]
    
    else :
        t3 = (l[i] + cur_t - cur_v) / 2
        if t3 >= t[i] :
            t3 = t[i]
        ret += (t3 - cur_t) * (2 * cur_v + t3 - cur_t) / 2
        ret += (t[i] - t3) * (2 * (cur_v + t3 - cur_t) - (t[i] - t3)) / 2
        if t3 == t[i] :
            cur_v = cur_v + t[i] - cur_t
        else :
            cur_v = l[i] - t[i]
    cur_t = t[i]
    
print(ret)

Submission status: Accepted

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

for i in range(n):
    l+=[v[i]]*t[i]*2

l=[min(i,j) for i,j in zip([0]+l,l+[0])]

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

ans=0

for i in range(1,len(l)):
    ans+=0.25*(l[i]+l[i-1])

print(ans)

Submission status: Accepted

Solution code:
f=lambda line,x:line[0]*x+line[1]
def _add_line(line,k,l,r):
    m=(l+r)//2
    if not data[k]:
        data[k]=line
        return
    lx,mx,rx=X[l],X[m],X[r-1]
    left,mid,right=f(line,lx)<f(data[k],lx),f(line,mx)<f(data[k],mx),f(line,rx)<f(data[k],rx)
    if left and right:
        data[k]=line
        return
    if not left and not right:return
    if mid:data[k],line=line,data[k]
    if left!=mid:_add_line(line,2*k+1,l,m)
    else:_add_line(line,2*k+2,m,r)
def add_line(line,a,b):
    L,R=a+N0,b+N0
    a0,b0=a,b
    sz=1
    while L<R:
        if R&1:
            R-=1
            b0-=sz
            _add_line(line,R-1,b0,b0+sz)
        if L&1:
            _add_line(line,L-1,a0,a0+sz)
            L+=1
            a0+=sz
        L>>=1
        R>>=1
        sz<<=1
def query(k):
    x=X[k]
    k+=N0-1
    s=10**18
    while k>=0:
        if data[k]:
            t=f(data[k],x)
            if t<s:s=t
        k=(k-1)//2
    return s
n,*t=map(int,open(0).read().split())
t,v=t[:n],t[n:]
st=sum(t)*2
m=a=i=0
N0=2**(st).bit_length()
data=[None]*(2*N0+1)
X=list(range(st+1))+[10**18]*N0
i=b=0
add_line((.5,0),0,st+1)
for u,w in zip(t,v):
    u+=u+i
    add_line((0,w),i,u)
    #add_line((1,b-i),i,st)
    #add_line((-1,w+u),0,u)
    add_line((-.5,w+i/2),0,i+1)
    add_line((.5,w-u/2),u,st+1)
    i,b=u,w
add_line((-.5,st/2),0,st+1)
a=x=0
for i in range(1,st+1):
    y=query(i)
    a+=(x+y)/4
    x=y
print(a)

Submission status: Accepted

Solution code:
f=lambda line,x:line[0]*x+line[1]
def _add_line(line,k,l,r):
    m=(l+r)//2
    if not data[k]:
        data[k]=line
        return
    lx,mx,rx=X[l],X[m],X[r-1]
    left,mid,right=f(line,lx)<f(data[k],lx),f(line,mx)<f(data[k],mx),f(line,rx)<f(data[k],rx)
    if left and right:
        data[k]=line
        return
    if not left and not right:return
    if mid:data[k],line=line,data[k]
    if left!=mid:_add_line(line,2*k+1,l,m)
    else:_add_line(line,2*k+2,m,r)
def add_line(line,a,b):
    L,R=a+N0,b+N0
    a0,b0=a,b
    sz=1
    while L<R:
        if R&1:
            R-=1
            b0-=sz
            _add_line(line,R-1,b0,b0+sz)
        if L&1:
            _add_line(line,L-1,a0,a0+sz)
            L+=1
            a0+=sz
        L>>=1
        R>>=1
        sz<<=1
def query(k):
    x=X[k]
    k+=N0-1
    s=10**18
    while k>=0:
        if data[k]:
            t=f(data[k],x)
            if t<s:s=t
        k=(k-1)//2
    return s
n,*t=map(int,open(0).read().split())
t,v=t[:n],t[n:]
st=sum(t)*2
m=a=i=0
N0=2**(st).bit_length()
data=[None]*(2*N0+1)
X=list(range(st+1))+[10**18]*N0
i=b=0
add_line((.5,0),0,st+1)
for u,w in zip(t,v):
    u+=u+i
    add_line((0,w),i,u)
    add_line((-.5,w+i/2),0,i+1)
    add_line((.5,w-u/2),u,st+1)
    i,b=u,w
add_line((-.5,st/2),0,st+1)
a=x=0
for i in range(1,st+1):
    y=query(i)
    a+=(x+y)/4
    x=y
print(a)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = S()
    t = S()
    ansa = []
    anslis = []
    lisans = []
    for i in range(len(s)):
        for j in range(len(t)):
            if 0 <= i + j < len(s) and (s[i + j] == t[j] or s[i + j] == "?"):
                continue
            break
        else:
            ansa.append((i, i + j))
    if len(ansa) == 0:
        print("UNRESTORABLE")
        return
    for ans in ansa:
        a = ""
        for num in range(len(s)):
            i = s[num]
            if ans[0] <= num <= ans[1]:
                i = t[num-ans[0]]
            a += i
        anslis.append(a)
    for ans in anslis:
        k = ""
        for i in ans:
            if i == "?":
                k += "a"
            else:
                k += i
        lisans.append(k)
    lisans.sort()
    print(lisans[0])
        
    return

# D
# 解説AC
# なんていうか脳みそが足りない
# 制限速度に落とし込むのはわかったけど。。。
# 一つの制限速度にに対して
# 0<=x<=l なら v+(l-x) 
# l<=x<=r なら v 
# r<=x<=T なら v+(x-r)
# つらい

def D():
    n = II()
    t = LI()
    v = LI()
    t += [0]
    v = [0] + v + [0]
    time = [[0, 0]]
    for i in range(1, n+2):
        time.append((time[-1][1], time[-1][1] + t[i - 1]))
    def vx(x):
        res = inf
        for i in range(n+2):
            res = min(res, f(i, x))
        return res
    def f(i, x):
        l, r = time[i]
        vi = v[i]
        return vi + (l - x) if 0 <= x <= l else vi if l <= x <= r else vi + (x - r)
    ans = 0
    for x in range(sum(t) * 2):
        ans += 0.25 * (vx(x/2) + vx(x/2 + 0.5))
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

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

operations = T[:]
v_limits = V[:]

v = 0
limits_x = [0]
for i in range(N):
    for _ in range(operations[i]*2):
        v += 0.5
        limit = min(v, v_limits[i])
        limits_x.append(limit)
        v = limit
        
        
v = 0
limits_y = [0]
for i in reversed(range(N)):
    for _ in range(operations[i]*2):
        v += 0.5
        limit = min(v, v_limits[i])
        limits_y.append(limit)
        v = limit
limits_y = list(reversed(limits_y))
#print(limits_x)
#print(limits_y)

limits_z = [min(x,y) for x, y in zip(limits_x, limits_y)]
#print(limits_z)

ans = 0
for _z, z in zip(limits_z[:-1],limits_z[1:]):
    ans += (_z+z)*0.5/2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

t = [int(x) for x in input().split()]
vSection = [int(x) for x in input().split()]

vPoint = [0]
for i in range(1, N):
	vPoint.append(min(vSection[i - 1], vSection[i]))
vPoint.append(0)

for i in reversed(range(1, N + 1)):
	if t[i - 1] < vPoint[i - 1] - vPoint[i]:
		vPoint[i - 1] = t[i - 1] + vPoint[i]


ans = 0
VE = 0
for i in range(N):
	VS = VE
	if VS + t[i] <= vPoint[i + 1]:
		VE = VS + t[i]
		ans += VS * t[i] + t[i] ** 2 / 2
	else:
		VE = vPoint[i + 1]
		sumT = sum(t[:i])
		a = VS - (0 if i == 0 else sumT)
		b = VE + sum(t[:i+1])
		y = (a + b) / 2
		if y >= vSection[i]:
			t1 = vSection[i] - VS
			t2 = vSection[i] - VE
			ans += VS * t1 + t1 ** 2 / 2 + vSection[i] * (t[i] - t1 - t2) + VE * t2 + t2 ** 2 / 2
		else:
			x = y - a
			ans += VS * (x - sumT) + (x - sumT) ** 2 / 2 + VE * (t[i] - (x - sumT)) + (t[i] - (x - sumT)) ** 2 / 2
			
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N = int(input())
t, v = list(map(int, input().split())), list(map(int, input().split()))
s = sum(t)*2
u = [[0.5*i, 0.5*(s-i)] for i in range(s+1)]
T = [0] * (N+1)
for i in range(N):
    T[i+1] = T[i]+t[i]
for i in range(s):
    now = 0.5*i
    for j in range(N):
        if now < T[j]:
            u[i].append(v[j]+T[j]-now)
        elif T[j] <= now <= T[j+1]:
            u[i].append(v[j])
        else:
            u[i].append(v[j]+now-T[j+1])
for i in range(s+1):
    u[i] = min(u[i])
ans = 0
for i in range(s):
    ans += (u[i]+u[i+1])/4
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import bisect


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

t = [0]+t
t = list(accumulate(t))

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


a = [0]

for i in range(1,(t[-1])*2+1):
    j = i/2
    b = bisect.bisect_left(t,j)
    a.append(min(a[-1]+1/2,v[b-1],v[b]+t[b]-j))
print(sum(a)/2)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))+[0]
for i in range(n-1,-1,-1):
    v[i]=min(v[i],v[i+1]+t[i])
ans=0
v0=0
for i in range(n):
    if v[i]<=v[i+1]:
        if v[i]-v0>t[i]:
            ans+=(2*v0+t[i])*t[i]/2
            v0=v0+t[i]
        else:
            ans+=t[i]*v[i]-(v[i]-v0)**2/2
            v0=v[i]
    else:
        if v[i]*2-v0-v[i+1]<t[i]:
            ans+=t[i]*v[i]-(v[i]-v0)**2/2-(v[i]-v[i+1])**2/2
            v0=v[i+1]
        elif v[i+1]-v0>t[i]:
            ans+=(2*v0+t[i])*t[i]/2
            v0=v0+t[i]
        else:
            d=abs(v0-v[i+1])
            ans+=max(v0,v[i+1])*t[i]-d**2/2+(t[i]-d)**2/4
            v0=v[i+1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
t = [int(Ti) for Ti in input().split()]
v = [int(Vi) for Vi in input().split()]

v_max = [0]
for ti, vi in zip(t, v):
    v_max[-1] = min(v_max[-1], vi)
    for _ in range(2*ti):
        v_max.append(vi)

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

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

area = 0
for i in range(len(v_max) - 1):
    area += 0.5 * 0.5 * (v_max[i] + v_max[i+1])

print(area)

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
T = [int(s) for s in input().split()]
V = [int(s) for s in input().split()] + [0]
lt = sum(T)
S = list(accumulate(T))

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

vel2 = [0] * (2 * lt + 1)
for i in range(len(T)):
    ti = T[i]
    tr = S[i]
    for ts in range(tr - ti, tr):
        for t in (2 * ts + 1, 2 * ts + 2):
            if vel2[t-1] - (2 * tr - (t - 1)) == 2 * V[i+1]:
                vel2[t] = vel2[t-1] - 1
            elif vel2[t-1] == 2 * V[i]:
                vel2[t] = vel2[t-1]
            else:
                vel2[t] = vel2[t-1] + 1
ans = sum([(vel2[t-1] + vel2[t]) / 8 for t in range(1, 2 * lt + 1)])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def mileage(t, v, vl, vr):
    assert(0 <= vl <= v and 0 <= vr <= v)
    # 最高速度v, 左端での速度vl, 右端での速度vr, 秒数tの時の走行距離を求める
    l = v-vl
    r = t-(v-vr)
    if l > r:
        tmp = (l+r)/2
        l = tmp
        r = tmp
    ret = 0
    ret += l*l/2+vl*l
    ret += (r-l)*v
    ret += (t-r)*vr+(t-r)*(t-r)/2
    return ret

def main():
    n = ri()
    lt = rli()
    lv = rli()
    lt.append(0)
    lv.append(0)
    lefts = [0] # 各区間の左端での列車の速度
    for i in range(n):
        left = min(lefts[i]+lt[i], lv[i], lv[i+1])
        offset = 0
        for j in range(i+1, n+1):
            left = min(left, offset+lv[j])
            offset += lt[j]
        lefts.append(left)
    # print(lefts)
    ans = 0
    for i in range(n):
        ans += mileage(lt[i], lv[i], lefts[i], lefts[i+1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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[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

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

Submission status: Accepted

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

# if N == 1: #最初の1区間だけ
#     if t[0] % 2 == 1: #奇数秒
#         if t[0]/2 < v[0]:
#             print ((t[0]/2) ** 2)
#             exit()
        

# print ('t', t)
# print ('v', v)
N_INF = - 10 ** 15
DP = [[N_INF] * (102) for _ in range(100 * 200 + 2)] #DP[T][V] := 時刻Tに速度Dで走っているときの時刻Tまでの走行距離の最大値
DP[0][0] = 0
# print (DP[0][0:5])
time = 1
for i in range(N):
    # print (i)
    # print ('time', time)
    for j in range(time, time + t[i]): #時刻
        # print (j, end = ' ')
        for k in range(0, v[i] + 1): #速度
            if k == 0: #速度0-->加速して速度0になることはない
                # print (j, k)
                # print (max(DP[j - 1][0], DP[j - 1][1] +  1/2))
                DP[j][k] = max(DP[j - 1][0] + 0.25, DP[j - 1][1] + 1/2)
            elif k != v[i]: #加速してくるときも減速してくることもある
                DP[j][k] = max(DP[j - 1][k -1] + k - 1/2, DP[j - 1][k] + k + 0.25, DP[j - 1][k + 1] + k + 1/2)
            else: #(k == v[i] and j != time) #減速してくることはない
                DP[j][k] = max(DP[j - 1][k -1] + k - 1/2, DP[j - 1][k] + k)
        # print (DP[j][0:5])
    time += t[i]
# print (time)
print (DP[time - 1][0])
# print ('T = 6, V = 6', DP[6][6])
# print ('T = 12, V = 2', DP[12][2])
# print ('T = 12, V = 3', DP[12][3])
# print ('T = 13, V = 2', DP[13][2])
# print ('T = 26 V = 2', DP[26][2])
# print ('T = 27 V = 2', DP[27][2])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC76 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

st = sum(t)
maxv = [0]
for i in range(n):
    maxv[-1] = min(maxv[-1],v[i])
    for _ in range(2*t[i]):
        maxv.append(v[i])
maxv[-1] = 0
for i in range(1,2*st+1):
    maxv[i] = min(maxv[i],maxv[i-1] + 0.5)
for i in range(2*st)[::-1]:
    maxv[i] = min(maxv[i],maxv[i+1] + 0.5)
ans = 0
for i in range(2*st):
    ans += (maxv[i] + maxv[i+1])*0.5 / 2
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

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

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N = i_inpl()
    t = l_inpl()
    v = l_inpl()

    T = sum(t)
    max_v = [0]

    for i in range(N):
        max_v[-1] = min(v[i], max_v[-1])
        max_v.extend([v[i]]*t[i]*2)

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

    max_v[-1] = 0
    for i in range(2*T-1, 0, -1):
        max_v[i] = min(max_v[i+1]+0.5, max_v[i])
    
    # for i, v in enumerate(max_v):
    #     print(i/2, v)
    ans = 0
    for i in range(2*T-1):
        ans += max_v[i] * 0.5 + (max_v[i+1]-max_v[i]) * 0.5
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
inpt=list(map(int,input().split()))
inpv=list(map(int,input().split()))

t=inpt+[0]
v=inpv+[0]

T=sum(t)
M=[0]

nowt=2*t[0]
nowmaxv=v[0]
nowv=M[0]
i=0

for time in range(2*T):
    if nowv+0.5<=v[i]:
        M.append(nowv+0.5)
    else:
        M.append(nowv)
    nowt-=1
    nowv=M[-1]
    if nowt==0:
        i+=1
        nowt=2*t[i]
        nowmaxv=v[i]
        nowv=min(nowv,nowmaxv)
        
t=list(reversed(inpt))+[0]
v=list(reversed(inpv))+[0]
m=[0]

nowt=2*t[0]
nowmaxv=v[0]
nowv=M[0]
i=0

for time in range(2*T):
    if nowv+0.5<=v[i]:
        m.append(nowv+0.5)
    else:
        m.append(nowv)
    nowt-=1
    nowv=m[-1]
    if nowt==0:
        i+=1
        nowt=2*t[i]
        nowmaxv=v[i]
        nowv=min(nowv,nowmaxv)

ans=[min(M[i],m[-i-1]) for i in range(len(M))]
print(sum([min(ans[i],ans[i+1])+(ans[i+1]-ans[i])**2 for i in range(len(ans)-1)])/2)

Submission status: Accepted

Solution code:
N = int(input())
*T, = map(int, input().split())
*V, = map(int, input().split())
speed = [0] # speed[i]: speed of train after 0.5*i seconds
for t, v in zip(T, V):
    speed[-1] = min(speed[-1], v)
    speed += [v]*(2*t)
speed[-1] = 0
temp = 0
for t in range(1, len(speed)):
    speed[t] = temp =  min(speed[t], temp + 0.5)
temp = 0
for t in range(len(speed)-1, 0, -1):
    speed[t] = temp =  min(speed[t], temp + 0.5)
ans = sum((v1 + v2)/4 for v1, v2 in zip(speed, speed[1:]))
print(ans)