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,M = map(int, input().split())
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

from itertools import accumulate as acm
T = [0] + list(acm(T))
V = V + [0]

nowSp = 0
dis = 0
nowTime = 0
from bisect import bisect_left as bl

while nowTime < T[-1]:
    nowTime += 0.5

    minV = min(T[i] - nowTime + V[i] for i in range(len(T)) if T[i] >= nowTime)    
    idx = bl(T, nowTime)-1
    minV=min(minV,V[idx])
    
    if minV > nowSp:
        minV = min(minV, nowSp + 0.5)
    if minV < nowSp:
        minV = min(minV, nowSp - 0.5)
    dis += (nowSp + minV) / 2 * 0.5
    nowSp = minV

print(dis)

Submission status: Accepted

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

time = sum(ts) + 1
speed_l = [0] * time
speed_r = [0] * time 

t_id = 0
speed = 0
ts_copy = ts[:]
# Forward
for i in range(time+1):
    ts_copy[t_id] -= 1
    speed_l[i] = speed
    if speed >= vs[t_id]:
        speed = vs[t_id]
    else:
        speed += 0.5 

    if ts_copy[t_id] == 0:
        if t_id + 1 >= n:
            break
        t_id += 1

# Backward
speed = 0
for i in range(time-1, -1, -1):
    ts[t_id] -= 1
    speed_r[i] = min(speed, speed_l[i])
    if speed >= vs[t_id]:
        speed = vs[t_id]
    else:
        speed += 0.5 

    if ts[t_id] == 0:
        if t_id <= 0:
            break
        t_id -= 1

print(sum(speed_r) / 2.0)

Submission status: Accepted

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')]*(T[-2]+1)
for t in range(len(vt)):
    now=t
    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):
    if abs(vt[i+1]-vt[i])==1:
        ans+=0.5*(vt[i]+vt[i+1])
    elif vt[i+1]==vt[i]:
        for k in range(N+2):
            if T[k]<=i and i+1<=T[k+1]:
                vv=V[k]
                break
        if vv>vt[i]:
            ans+=0.5*(vt[i]*2+0.5)
        else:
            ans+=vt[i]
print(ans)

Submission status: Accepted

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

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
res = sum(dp)*2-dp[0]-dp[-1]
print(res*0.25)

Submission status: Accepted

Solution code:
N = int(input())
T = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]

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

for i in range(len(maxv) - 1):
    maxv[i + 1] = min(maxv[i + 1], maxv[i] + 0.5) 
    
for i in reversed(range(len(maxv) - 1)):
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)
    
ans = 0
for i in range(len(maxv) - 1):
    ans += (maxv[i] + maxv[i + 1]) * 0.5 / 2
    
print(ans)

Submission status: Accepted

Solution code:
N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
vtmax=[0]
tmp=0
Tsum=sum(T)
for t,v in zip(T,V):
    vtmax[-1]=min(tmp,v) #境界は小さい方が制約
    vtmax+=[v]*(t*2)
    tmp=v
vtmax[-1]=0

for i in range(1,2*Tsum):
    vtmax[i]=min(vtmax[i],vtmax[i-1]+0.5)
for i in range(2*Tsum-1,0,-1):
    vtmax[i]=min(vtmax[i],vtmax[i+1]+0.5)
area=0
for i,vt in enumerate(vtmax):
    if i==0:continue
    area+=0.5*(vt+vtmax[i-1])/2
print(area)

Submission status: Accepted

Solution code:
def atcoder_express(N: int, T: list, V: list)->float:
    MAXT = sum(T)
    graph = [0] * (2*MAXT + 1)

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

    V = [0] + V + [0]

    conditions = []
    for i in range(N+2):
        v, l, r = V[i], T[i], T[i+1]
        conditions.append((l, r, v))

    total = 0.0
    prev_v = 0.0
    for t in range(MAXT*2+1):
        min_v = float('inf')
        x = t / 2
        for l, r, v in conditions:
            if x < l:
                min_v = min(min_v, v + (l - x))
            elif r < x:
                min_v = min(min_v, v + (x - r))
            else:
                min_v = min(min_v, v)
        total += (prev_v + min_v) * 0.5 / 2
        prev_v = min_v

    return total


if __name__ == "__main__":
    N = int(input())
    T = [int(s) for s in input().split()]
    V = [int(s) for s in input().split()]
    ans = atcoder_express(N, T, V)
    print(ans)

Submission status: Accepted

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

    ans = editorial(N, t, v)
    print(ans)
    # time: sum(t) seconds
    # t_n: v_n m/s 以内
    # a: +- 1 m/s^2
    # => ???
    # answer: max dist

    # 現時点の制限速度MAXで走ると距離は伸びるが
    # 次のスタート時点の制限速度を考慮しないとルール違反となる
    # 最初と最後は速度0
    # 次と比較しても次々にて速度Overする可能性がある…


def editorial(N, ts, vs):
    maxv = []
    for v, t in zip(vs, ts):
        maxv.extend([v] * 2 * t)

    # 入力例3
    # [0]-----------[12]-------------[26]-[28]
    # 0,6-----------6,2 -------------2,7 -7,0
    # 0,6-----------6,2 -------------2,7,7,7
    # 6,6---------6,2,2 -----------2,7,7,7,0
    # ↓
    # 6,6--------- 6,2,2 -----------2,7,7
    # 6 ---------- 2,2 -----------2,7,7,x
    # 前から0ベース
    # 後から0ベースでの比較
    maxv = [0] + [min(v1, v2) for v1, v2 in zip(maxv, maxv[1:])]
    maxv.append(0)

    max_t = len(maxv)
    bef_v = 0
    for i in range(max_t):
        bef_v = maxv[i] = min(maxv[i], bef_v + 0.5)
    aft_v = -0.5
    for i in range(max_t)[::-1]:
        aft_v = maxv[i] = min(maxv[i], aft_v + 0.5)

    ans = 0
    for v1, v2 in zip(maxv, maxv[1:]):
        ans += (v1 + v2) * 0.5 / 2

    return ans


def fix_maxv(maxv, max_t):
    """
    0123456789 -> t
      2--23--3 -> v

      のように見えるけど実際は違う

    """
    maxv = maxv[:]
    tmp = [None] * 3
    tmp[0] = maxv[:]
    bef_v = 0
    for i in range(max_t):
        bef_v = maxv[i] = min(maxv[i], bef_v + 0.5)

    # lastが 0.5にならず、0m/s になるように調整
    tmp[1] = maxv[:]
    aft_v = -0.5
    for i in range(max_t)[::-1]:
        aft_v = maxv[i] = min(maxv[i], aft_v + 0.5)
    tmp[2] = maxv[:]
    for i in range(max_t):
        print(*([0.5 + i/2] + [tmp[j][i] for j in range(3)]), sep="\t")

    return maxv


def editorial_WA(N, ts, vs):
    # サンプル4より、0.5刻みで考える必要あり
    maxv = []
    for v, t in zip(vs, ts):
        maxv.extend([v] * 2 * t)
    default_maxv = [v + 0.05 for v in maxv]

    max_t = sum(ts) * 2
    maxv = fix_maxv(maxv, max_t)

    import os
    # atcoder uname
    # posix.uname_result(sysname='Linux', nodename='imojudge-all', release='3.13.0-108-generic',
    #                    version='#155-Ubuntu SMP Wed Jan 11 16:58:52 UTC 2017',
    #                    machine='x86_64')
    local = "Darwin" in str(os.uname())
    if local:
        import matplotlib
        # matplotlib.use("Qt4Agg")
        matplotlib.use("TkAgg")
        import matplotlib.pyplot as plt
        real_ts = [i / 2 for i in range(1, len(maxv) + 1)]
        plt.plot(real_ts, maxv, color="red")
        plt.plot(real_ts, default_maxv, color="blue")
        plt.show()
        # plt.show(block=False)
        # plt.pause(.01)

    ans = 0
    # lastを0m/s に調整するために + [0]
    # しかし合計0.5 秒余計, この調整をやめることでlastが0.5m/s のまま
    # for t, (v1, v2) in enumerate(zip([0] + maxv, maxv + [0]), 1):
    for t, (v1, v2) in enumerate(zip([0] + maxv, maxv), 1):
        # 台形面積
        trapezoid = (v1 + v2) * 0.5 / 2
        ans += trapezoid
        if local:
            print(t / 2, v1, v2, trapezoid, ans, sep="\t")

    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N = int(input())
    T = list(map(int, input().split()))
    V_limit = list(map(int, input().split()))

    V = []
    for i in range(N):
        V += [V_limit[i] for _ in range(2 * T[i])]

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

    V = [0] + V
    V[-1] = 0

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
time = list(map(int, input().split()))
speed = list(map(int, input().split()))
speed = [0] + speed + [0]
cumtime = [0] * (n+1)
for i in range(n):
    cumtime[i+1] = cumtime[i] + time[i]
dis = 0.0
prev = 0
l = cumtime[n]
tp = 1
for t in range(1, l+1):
    if t > cumtime[tp]:
        tp += 1
    v = speed[tp]
    v = min(v, prev + 1)
    for i in range(tp):
        v = min(v, t - cumtime[i] + speed[i])
    for i in range(tp+1, n+2):
        v = min(v, cumtime[i-1] - t + speed[i])
    if v == prev and v < speed[tp]:
        dis += v + 1/4
    else:
        dis += (v + prev) / 2
    prev = v
print(dis)

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    r,g = IR(2)
    print(2*g-r)

#B
def B():
    n = I()
    k = I()
    a = 1
    for i in range(n):
        if a > k:
            a += k
        else:
            a *= 2
    print(a)
#C
def C():
    def check(a,b):
        for i in range(len(a)):
            if a[i] != b[i] and a[i] != "?":
                return False
        return True
    def f(c):
        if c == "?":return "a"
        return c
    s = S()
    t = S()
    n = len(s)
    l = len(t)
    ans = []
    for i in range(n-l+1)[::-1]:
        if check(s[i:i+l],t):
            c = [f(s[j]) for j in range(i)]
            c += t
            for j in range(i+l,n):
                c += f(s[j])
            ans.append(c)
    if not len(ans):
        print("UNRESTORABLE")
    else:
        ans.sort()
        for i in ans[0]:
            print(i,end = "")
        print()
#D
def D():
    n = I()
    t = LI()
    v = LI()
    v.append(0)
    for i in range(n-1):
        t[i+1] += t[i]
    vt = defaultdict(int)
    k = 0
    for i in range(t[-1]*2+1):
        nt = i/2
        if nt >= t[k]:
            k += 1
        vt[nt] = v[k]
    for i in range(n)[::-1]:
        for j in range(t[i]*2+1)[::-1]:
            nt = j/2
            if -nt+v[i+1]+t[i] < vt[nt]:
                vt[nt] = -nt+v[i+1]+t[i]
    ans = 0
    nv = 0
    for i in range(1,t[-1]*2+1):
        nt = i/2
        if nv < vt[nt-0.5]:
            ans += 0.125+nv/2
            nv += 0.5
        elif nv == vt[nt]:
            ans += nv/2
        else:
            if nv > vt[nt]:
                nv -= 0.5
                ans += 0.125+nv/2
            else:
                ans += nv/2
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

Solution code:
from itertools import chain
  
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
  
va = list(chain.from_iterable([v] * (2 * t) for t, v in zip(ts, vs)))
va = [min(v1, v2) for v1, v2 in zip([0] + va, va + [0])]
lt = len(va)
  
pv = 0
for ct in range(1, lt):
    va[ct] = pv = min(va[ct], pv + 0.5)
  
pv = 0
for ct in range(lt - 1, 0, -1):
    va[ct] = pv = min(va[ct], pv + 0.5)
  
print(sum((v1 + v2) / 4 for v1, v2 in zip(va, va[1:])))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    C = [0] * (N+1)
    for i in range(N-1):
        C[i+1] = min(V[i], V[i+1])
    for _ in range(N):
        for i in range(N):
            left = C[i]
            right = C[i+1]
            C[i] = min(C[i], right + T[i])
            C[i+1] = min(C[i+1], left + T[i])
    ans = 0
    for i in range(N):
        if (V[i] - C[i]) + (V[i] - C[i+1]) < T[i]:
            lx = V[i] - C[i]
            rx = V[i] - C[i+1]
            ans += (C[i] + V[i]) * lx / 2 + \
                (C[i+1] + V[i]) * rx / 2 + \
                V[i] * (T[i]-lx-rx)
        else:
            M = max(C[i], C[i+1])
            m = min(C[i], C[i+1])
            x = (T[i] - (M-m)) / 2
            ans += (M + M+x) * x / 2 + (m + M+x) * (x+(M-m)) / 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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
    if i-1 >= 0 and V[i-1] > V[i] :
        while le >= 0 :
            M[le] = min(M[le], V[i] + j*bg)
            #print(M[le])
            j += 1
            le -= 1
    j = 0
    if i+1 < n and V[i+1] > V[i] :
        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: Accepted

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

maxv = [0] # vel=0 at initial
for v,t in zip(vs,ts):
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t*2):
        maxv.append(v)
maxv[-1] = 0 # vel=0 at last
T = len(maxv)
# print(T)

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

for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i+1]+0.5)
    
ans = 0
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1])/4
print(ans)

Submission status: Accepted

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
    sptmp[:t0 * 2] += np.arange(t0, 0, -0.5)
    sptmp[t1 * 2:] += np.arange(0, accT[-1] - t1 + 0.5, 0.5)
    speeds = np.minimum(speeds, sptmp)

ans = sum(speeds) / 2

print(ans)

Submission status: Accepted

Solution code:
# FROM : https://atcoder.jp/contests/abc076/submissions/3723095
N = int(input()) 
T = list(map(lambda x: int(x)*2, input().split()))
V = list(map(lambda x: int(x)*2, input().split())) + [0]

sumt = sum(T)
maxv  = [min(i,sumt-i) for i in range(sumt+1)]

ct = 0
for t,v in zip(T,V):
    for i in range(ct, ct+t+1):
        maxv[i] = min(maxv[i], v)
    ct += t

for i in range(sumt):
    maxv[i+1] = min(maxv[i+1], maxv[i]+1)

for i in reversed(range(sumt)):
    maxv[i] = min(maxv[i], maxv[i+1] + 1)

print(float( sum(maxv) ) / 4)

Submission status: Accepted

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
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2 #左側
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2 #右側
        area -=  max(0, (kouten_v - v_max))** 2 #上の三角形
    else:
        area = (v_start + v_end) *  dt / 2
    return area

def main():
    #与えられた入力を受け取る
    n=int(input())
    t=[int(i) for i in input().split()]
    v=[int(i) for i in input().split()]

    #各区間の許容最大速度を計算する
    #（この段階では傾きが-1未満になる可能性がある）
    max_velocity = [0]
    for i in range(1, n):
        max_velocity_ = min(v[i-1], v[i], max_velocity[i-1] + t[i-1])
        max_velocity.append(max_velocity_)
    max_velocity.append(0)

    #後ろから走査して、傾きが-1以上を満たすように許容速度をfittingする
    for i in range(n-1):
        if  max_velocity[-(i+1)] - max_velocity[-(i+2)] < -t[-(i+1)]:
            max_velocity[-(i+2)] = max_velocity[-(i+1)] + t[-(i+1)]

    #各区間の面積を計算して足し合わせる
    ans = 0
    for i in range(n):
        ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
    print(ans)

main()

Submission status: Accepted

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
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2 #左側
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2 #右側
        area -=  max(0, (kouten_v - v_max))** 2 #上の三角形
    else:
        area = (v_start + v_end) *  dt / 2
    return area

def main():
    #与えられた入力を受け取る
    n=int(input())
    t=[int(i) for i in input().split()]
    v=[int(i) for i in input().split()]

    #各区間の許容最大速度を計算する
    #（この段階では傾きが-1未満になる可能性がある）
    max_velocity = [0]
    for i in range(1, n):
        max_velocity_ = min(v[i-1], v[i], max_velocity[i-1] + t[i-1])
        max_velocity.append(max_velocity_)
    max_velocity.append(0)

    #後ろから走査して、傾きが-1未満を満たすように許容速度をfittingする
    for i in range(n-1):
        if  max_velocity[-(i+1)] - max_velocity[-(i+2)] < -t[-(i+1)]:
            max_velocity[-(i+2)] = max_velocity[-(i+1)] + t[-(i+1)]

    #各区間の面積を計算して足し合わせる
    ans = 0
    for i in range(n):
        ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
    print(ans)

main()

Submission status: Accepted

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

Solution code:
N = int(input())
t = [0] + list(map(int, input().split())) + [0]
v = [0] + list(map(int, input().split())) + [0]
for i in range(N, 0, -1):
    v[i] = min(v[i], v[i + 1] + t[i])
for i in range(1, N + 1):
    v[i] = min(v[i], v[i - 1] + t[i])
ans = 0
v_f = 0
for i in range(1, N + 1):
    v_l = min(v_f + t[i], v[i + 1], v[i])
    if 2 * v[i] - v_f - v_l <= t[i]:
        ans += (v[i] + v_f) * (v[i] - v_f) / 2 + v[i] * (t[i] - 2 * v[i] + v_f + v_l) + (v[i] + v_l) * (v[i] - v_l) / 2
    else:
        t_1 = (t[i] + v_l - v_f) / 2
        t_2 = t[i] - t_1
        ans += (2 * v_f + t_1) * t_1 / 2 + (2 * v_l + t_2) * t_2 / 2
    v_f = v_l
print('{:.10f}'.format(ans))

Submission status: Accepted

Solution code:
n = int(input())
t = [int(m) for m in input().split()]
T = sum(t)
v = [int(m) for m in input().split()]
v.append(0)
#maxv[i]
maxv=[0]
#maxv = []
i = 0
cnt = 0
#for i in range(2*T):
while i < n:
    cnt += 0.5
    if t[i] == cnt:
        maxv.append(min(v[i],v[i+1]))
        i += 1
        cnt = 0
    else:
        maxv.append(v[i])
maxv[0] = 0
#maxv.append(0)
maxv[2*T] = 0

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
t_list = list(map(int, input().split()))
v_list = list(map(int, input().split()))
t_sum = sum(t_list)
v_max = [0.0] * (2 * t_sum + 1)

t_i = 0
v_i = 0
t = t_list[t_i]
v = v_list[v_i]
time = 0
for i in range(1, 2 * t_sum + 1):
    time += 0.5
    if time >= t:
        time = 0
        t_i += 1
        v_i += 1
        if t_i >= N:
            break
        t = t_list[t_i]
        v_max[i] = min(min(v, v_list[v_i]), v_max[i - 1] + 0.5)
        v = v_list[v_i]
        continue
    v_max[i] = min(v, v_max[i - 1] + 0.5)

t_i = N - 1
v_i = N - 1
t = t_list[t_i]
v = v_list[v_i]
v_max[-1] = 0
time = 0
for i in range(2 * t_sum - 1, -1, -1):
    time += 0.5
    if time >= t:
        t_i -= 1
        v_i -= 1
        if t_i < 0:
            break
        t = t_list[t_i]
        v = v_list[v_i]
        time = 0
    if v_max[i] > v_max[i + 1] + 0.5:
        v_max[i] = v_max[i + 1] + 0.5

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

Submission status: Accepted

Solution code:
INF = 10 ** 20
n = int(input())
tlst = list(map(int, input().split()))
vlst = list(map(int, input().split()))
dp = [[-INF] * 201 for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    t, v = tlst[i], vlst[i]
    for v_fr in range(v + 1):
        pre_score = dp[i][v_fr]
        for v_to in range(v + 1):
            diff = abs(v_to - v_fr)
            if diff > t:continue
            max_speed = min((v_to + v_fr + t) / 2, v)
            dp[i + 1][v_to] = max(dp[i + 1][v_to], pre_score + max_speed * t - (max_speed - v_to) ** 2 / 2 - (max_speed - v_fr) ** 2 / 2)
print(dp[n][0])

Submission status: Accepted

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

dp = [[-float('inf')]*(101) for _ in range(N+1)]
V.append(0)

dp[0][0] = 1

for i in range(N):
    for v in range(V[i]+1):
        for vv in range(V[i]+1):
            past_dist = dp[i][v]
            if 2*V[i]-v-vv <= T[i]:
                a = V[i]-v
                b = V[i]-vv
                c = (v+V[i])*a/2 + V[i]*(T[i] - a - b) + (vv+V[i])*b/2
                dp[i+1][vv] = max(dp[i+1][vv], c+past_dist)
            elif T[i] >= abs(vv-v):
                ta = (vv-v+T[i])/2
                tb = (T[i]+v-vv)/2
                c = (2*v+ta)*ta/2 + (vv+v+ta)*tb/2
                dp[i+1][vv] = max(dp[i+1][vv], c+past_dist)

print(dp[N][0]-1)

Submission status: Accepted

Solution code:
"""
def func(n, t, v):
    t = [0] + t + [t[-1]]
    print("t:{}".format(t))
    v = [0] + v + [0]

    limit = [0 for _ in range(t[-1] + 1)]
    for i in reversed(range(len(t) - 1)):
        for j in range(t[i] - t[i-1]):
            limit[t[i] - j] = min(v[i + 1] + j, v[i])

    print(limit)
    print([[i, limit[i]] for i in range(len(limit))])
    # print(list(range(len(limit))))
    dist = 0
    prev = 0
    for i in range(1, len(limit)):
        next = min(prev + 1, limit[i])
        dist += (next + prev) / 2
        print("i:{} add:{} dist:{}".format(i, (next + prev) / 2, dist))
        prev = next
    return str(dist)
"""
def func(n, t, v):
    t = [0] + t + [t[-1]]
    v = [0] + v + [0]
    for i in range(len(t)):
        t[i] *= 2
    for i in range(len(v)):
        v[i] *= 2
    # print("t:{}".format(t))

    limit = [0 for _ in range(t[-1] + 1)]
    for i in reversed(range(len(t) - 1)):
        for j in range(t[i] - t[i-1]+1):
            limit[t[i] - j] = min(limit[t[i]] + j, v[i])

    # print(limit)
    # print([[i, limit[i]] for i in range(len(limit))])
    # print(list(range(len(limit))))
    dist = 0
    prev = 0
    for i in range(1, len(limit)):
        next = min(prev + 1, limit[i])
        dist += (next + prev) / 2
        # print("i:{} add:{} dist:{}".format(i, (next + prev) / 2, dist))
        prev = next
    return str(dist/4)

# print(510*510/2)
n = int(input())
t = [int(i) for i in input().split()]
for i in range(1, len(t)):
    t[i] += t[i-1]
v = [int(i) for i in input().split()]
print(func(n, t, v))
# print("print(func({}, {}, {}))".format(n, t, v))
"""
print("2100 vs " + func(1, [100], [30]) + "\n")
print("2632 vs " + func(2, [60, 110], [34, 38]) + "\n")
print("76 vs " + func(3, [12, 26, 28], [6, 2, 7]) + "\n")
print("20.25 vs " + func(1, [9], [10]) + "\n")
print(
    "20291 vs " + func(10, [64, 119, 146, 181, 257, 376, 383, 401, 450, 550], [29, 19, 31, 39, 27, 48, 41, 87, 55, 70]))
"""

Submission status: Accepted

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

"""
参考：http://ferin-tech.hatenablog.com/entry/2017/10/28/231616
・愚直に3重ループでシミュレーション
"""

N = int(input())
tN = list(map(int, input().split()))
vN = list(map(int, input().split()))
# 終点の処理をしやすくするため追加
tN.append(0)
vN.append(0)

dist = 0
speed = 0
for i in range(N):
    keep = True
    plus = True
    # 小数刻みのfor文
    for j in [0.5*x for x in range(tN[i]*2)]:
        # 現在の最大スピードに達した
        if speed == vN[i]:
            plus = False
        rest = tN[i] - j
        # 今より先で、下げきれなくなる状況がないか確認
        for k in range(i+1, N+1):
            if vN[k] < vN[i] and rest <= speed - vN[k]:
                keep = False
                plus = False
            rest += tN[k]
        # フラグの状況に合わせて加速or維持or減速
        if plus:
            # ここでの数値の加減は進み方が0.5刻みなので注意する
            dist += speed/2
            speed += 0.5
            dist += 0.125
        elif keep:
            dist += speed/2
        else:
            speed -= 0.5
            dist += speed/2
            dist += 0.125
print(dist)

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 i in range(2 * t):
        maxv.append(v)

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

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

ans = 0
for i in range(T - 1):
    ans += (maxv[i] + maxv[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()))

MAX_V = [0]
# グラフを整える準備
for v, t in zip(V, T):
    # 転換地点では低い方に合わせる
    MAX_V[-1] = min(MAX_V[-1], v)
    for ti in range(t * 2):
        MAX_V.append(v)

# 前から
for i in range(1, len(MAX_V)):
    MAX_V[i] = min(MAX_V[i - 1] + 0.5, MAX_V[i])

MAX_V[-1] = 0
# 後ろから
for i in range(len(MAX_V) - 2, -1, -1):
    MAX_V[i] = min(MAX_V[i], MAX_V[i + 1] + 0.5)

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

print(ans)