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: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate
    dh = 100

    n = int(readline())
    t_ = [0] + list(map(int, readline().split()))
    t_list = list(accumulate(t_))
    v_list = list(map(int, readline().split())) + [0]
    lim = [0] * (sum(t_list) * dh + 1)

    for i in range(n):
        st = dh * t_list[i]
        nt = dh * t_list[i + 1]
        cv = v_list[i]
        pv = lim[st]
        nv = v_list[i + 1]
        for ct in range(st, nt + 1):
            lim[ct] = min(cv, pv + (ct - st) / dh, nv + (nt - ct) / dh)

    ans = 0
    pv = 0
    for v in lim[1:]:
        ans += (pv + (v - pv) / 2) / dh
        pv = v

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate

    n = int(readline())
    t_ = [0] + list(map(int, readline().split()))
    t_list = list(accumulate(t_))
    v_list = list(map(int, readline().split())) + [0]
    lim = [0] * (sum(t_list) * 2 + 1)

    for i in range(n):
        st = 2 * t_list[i]
        nt = 2 * t_list[i + 1]
        cv = v_list[i]
        pv = lim[st]
        nv = v_list[i + 1]
        for ct in range(st, nt + 1):
            lim[ct] = min(cv, pv + (ct - st) / 2, nv + (nt - ct) / 2)

    ans = 0
    pv = 0
    for v in lim[1:]:
        ans += 0.5 * (pv + (v - pv) / 2)
        pv = v

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate

    n = int(readline())
    t_ = [0] + list(map(int, readline().split()))
    t_list = list(accumulate(t_))
    v_list = list(map(int, readline().split())) + [0]
    lim = [0] * (sum(t_list) + 1)

    for i in range(n):
        st = t_list[i]
        nt = t_list[i + 1]
        cv = v_list[i]
        pv = lim[st]
        nv = v_list[i + 1]
        for ct in range(st, nt + 1):
            lim[ct] = min(cv, pv + (ct - st), nv + (nt - ct))

    ans = 0
    pv = 0
    for v in lim[1:]:
        ans += pv + (v - pv) / 2
        pv = v

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
dvl={}
dvr={}
T=sum(t)
tmp=0
v_pre=0
  
for i in range(n):
  t_span=t[i]
  v_now=v[i]
  for j in range(2*t_span):
    dvl[tmp+j/2]=min(v_now,v_pre+j/2)
  tmp+=t_span
  v_pre=dvl[tmp-1/2]
tmp=0
v_pre=0
for i in range(n-1,-1,-1):
  t_span=t[i]
  v_now=v[i]
  for j in range(2*t_span):
    dvr[T-(tmp+j/2+0.5)]=min(v_now,v_pre+0.5+j/2)
  tmp+=t_span
  v_pre=dvr[T-tmp]
ans=0
for i in range(T*2):
  ans+=min(dvl[i/2],dvr[i/2])/2
  #print(i/2,dvl[i/2],dvr[i/2])
print(ans)
#print(dvl)
#print(dvr)

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
t.append(0)
t.append(0)
v.append(0)
v.append(0)
ans=0
tmp=0
for i in range(n):
  t_span=t[i]
  v_pre=v[i-1]
  v_now=v[i]
  v_next=v[i+1]
  for j in range(2*t_span):
    d=min(v_now,v_pre+j/2,v_next+(2*t_span-j)/2)/2
    #print(j/2,d)
    ans+=d
print(ans)

Submission status: Wrong Answer

Solution code:
# Atcoder Express
from bisect import bisect_left, bisect_right
N = int(input())
time = list(map(int, input().split()))
vel = list(map(int, input().split()))
sum_t = [0 for i in range(N+1)]

for i in range(1, N+1):
    sum_t[i] = sum_t[i-1]+time[i-1]

dp = [[-float("inf") for j in range(101)] for i in range(20001)]
# dp[t][v]=開始からt秒後に速度v で走っている時に、t秒後に実現できる最大の移動距離
dp[0][0] = 0

for i in range(1, sum_t[-1]+1):
    # i秒後における更新

    bef = bisect_left(sum_t, i-1)
    phase = bisect_left(sum_t, i)

    bef_bound = vel[bef-1] # i-1秒時点における速度制限
    bound = vel[phase-1]    # i秒後における速度制限
    if bef == 0:
        bef_bound = 100

    for j in range(bound+1):
        if j == 0:
            if j+1 <= min(bef_bound,bound):
                    dp[i][j] = max(dp[i-1][j]+j+0.25, dp[i-1][j+1]+j+0.5)
            else:
                if j == min(bef_bound,bound):
                    dp[i][j] = dp[i-1][j]+j

        elif j >= 1:
            if j+1 <= min(bound,bef_bound):
                dp[i][j] = max(dp[i-1][j-1]+j-0.5, dp[i-1][j]+j+0.25, dp[i-1][j+1]+j+0.5)
            else:
                if j == min(bound,bef_bound):
                    dp[i][j] = max(dp[i-1][j-1]+j-0.5, dp[i-1][j]+j)
                else:
                    if j-1 == min(bef_bound,bound):
                        dp[i][j] = dp[i-1][j-1]+j-0.5

                        

ans = dp[sum_t[-1]][0]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
tl = list(map(int, input().split()))
vl = list(map(int, input().split()))

tsl = [0]
for i in range(n):
    tsl.append(sum(tl[:i+1]))

vl.append(0)
dl = []
for i,v in zip (tsl,vl):
    dl.append([i,v])

res = 0
nv = 0
nt = 0

for i in range(n):

    vmax = min(dl[i][1],dl[i+1][1])
    for j in range(i+1,n):
        vtmax = (dl[j][0] - dl[i+1][0])+dl[j][1]
        vmax = min(vmax,vtmax)

    if tl[i] >= (vl[i]-nv)+(vl[i]-vmax):
        res += (vl[i]+nv)*(vl[i]-nv)/2 + vl[i]*(tl[i]-((vl[i]-nv)+(vl[i]-vmax)))+(vl[i]+vmax)*(vl[i]-vmax)/2

        nv = vmax
        nt = dl[i+1][0]
    elif tl[i] >= abs(vmax-nv):
        if vmax >= nv:
            res += (nv+((tl[i]-(vmax-nv))/2 + vmax))*(tl[i]-(tl[i]-(vmax-nv))/2)/2 + (((tl[i]-(vmax-nv))/2 + vmax) +vmax)*((tl[i]-(vmax-nv))/2 ) /2 
        else:
            res += (nv+((tl[i]-abs(vmax-nv))/2 + nv))*((tl[i]-abs(vmax-nv))/2)/2 + (((tl[i]-abs(vmax-nv))/2 + nv) +vmax)*(tl[i]-(tl[i]-abs(vmax-nv))/2)/2             
        nv = vmax
        nt = dl[i+1][0]
    else:
        res += (nv + (nv+tl[i])) * tl[i] /2
        nv = nv +tl[i]
        nt = dl[i+1][0]

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
u = [0]
for vi, ti in zip(v, t):
  u[-1] = min(u[-1], vi)
  u += [vi] * ti

u[-1] = 0
U = u.copy()
T = len(u)
for i in range(1, T):
  u[i] = min(u[i], u[i-1]+1)

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

ans = 0
for i in range(1, T):
  if u[i] == u[i-1]:
    ans += u[i]
    if U[i] > u[i] or U[i-1] > u[i-1]:
      ans += 0.25
  else:
    ans += (u[i] + u[i-1]) / 2

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
u = [0]
for vi, ti in zip(v, t):
  u[-1] = min(u[-1], vi)
  u += [vi] * ti

u[-1] = 0
U = u.copy()
T = len(u)
for i in range(1, T):
  u[i] = min(u[i], u[i-1]+1)

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

ans = 0
for i in range(1, T):
  if u[i] == u[i-1]:
    ans += u[i]
    if U[i] > u[i]:
      ans += 0.25
  else:
    ans += (u[i] + u[i-1]) / 2

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    # scaling by 2 for avoiding float
    T = list(map(lambda t: int(t) * 2, input().split(' ')))
    V = list(map(lambda v: int(v) * 2, input().split(' ')))
    sum_t = sum(T)
    # create velocity lines
    cumsum_t = 0
    lines = [list() for _ in range(N)]
    for n in range(N):
        t, v = T[n], V[n]
        left_t, right_t = cumsum_t, cumsum_t + t
        # non-restricted case
        if right_t <= v or sum_t - left_t <= v:
            lines[n].extend([
                (0, 0, sum_t / 2, sum_t / 2),
                (sum_t / 2, sum_t / 2, sum_t, 0)
            ])
            continue
        # left part
        if left_t <= v:
            lines[n].append((0, 0, v, v))
        else:
            lines[n].extend([
                (0, 0, (left_t + v) / 2, (left_t + v) / 2),
                ((left_t + v) / 2, (left_t + v) / 2, left_t, v)
            ])
        # center part
        lines[n].append((max([left_t, v]), v, min([right_t, sum_t - v]), v))
        # right part
        if sum_t - right_t <= v:
            lines[n].append((sum_t - v, v, sum_t, 0))
        else:
            lines[n].extend([
                (right_t, v, (sum_t + right_t - v) / 2, (sum_t - right_t + v) / 2),
                ((sum_t + right_t - v) / 2, (sum_t - right_t + v) / 2, sum_t, 0)
            ])
        cumsum_t += t
    # minimum velocity lines
    max_v = max(V)
    min_v_lines = [max_v + 1 for _ in range(sum_t + 1)]
    min_v_lines[0] = 0
    for t in range(1, sum_t + 1):
        for n in range(N):
            for line in lines[n]:
                if line[0] <= t - 1 and t <= line[2]:
                    trend = (line[3] - line[1]) / (line[2] - line[0])
                    v = line[1] + trend * (t - line[0])
                    min_v_lines[t] = min([min_v_lines[t], v])
                    break
    # calculate answer
    ans, before_v = 0, 0
    for t in range(1, sum_t + 1):
        v = min_v_lines[t]
        ans += (before_v + v) / 2
        before_v = v
    print(ans / 4)  # scaling


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

vmax_l = [0 for _ in range(T+1)]
vmax_r = [0 for _ in range(T+1)]
vmax = [0 for _ in range(T+1)]
for i in range(1, T+1):
    tt = 0
    for j in range(n):
        if i > t[j]+tt:
            tt += t[j]
        else:
            vmax_l[i] = min(v[j], vmax_l[i-1]+1)
            break
for i in range(T-1, -1, -1):
    tt = T
    for j in range(n-1, -1, -1):
        if i < tt-t[j]:
            tt -= t[j]
        else:
            vmax_r[i] = min(v[j], vmax_r[i+1]+1)
            break
for i in range(T+1):
    vmax[i] = min(vmax_l[i], vmax_r[i])

point_t = [0]
point_v = [0]
for i in range(1, T):
    if vmax[i-1] != vmax[i] and vmax[i] == vmax[i+1]:
        point_t.append(i)
        point_v.append(vmax[i])
    elif vmax[i-1] == vmax[i] and vmax[i] != vmax[i+1]:
        point_t.append(i)
        point_v.append(vmax[i])
point_t.append(T)
point_v.append(0)
ans = 0
for i in range(1, len(point_t)):
    ans += (point_t[i]-point_t[i-1])*(point_v[i]+point_v[i-1])/2
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    Tall = sum(T)
    R = [0] * (Tall + 1)
    j = N - 1
    tc, vc, vn = T[-1], V[-1], V[-1]
    R[-1] = 0
    for i in reversed(range(Tall)):
        tc -= 1
        if tc == 0:
            j -= 1
            tc, vn = T[j], V[j]
        R[i] = min(R[i + 1] + 1, vc, vn)
        vc = vn
    v = 0
    d = 0.0
    j = 0
    tc, vc, vn = T[j], V[j], V[j]
    T.append(0)
    V.append(0)
    A = [0]
    for i in range(1, Tall + 1):
        tc -= 1
        if tc == 0:
            j += 1
            tc, vn = T[j], V[j]
        vnn = min(v + 1, R[i], vc, vn)
        d += (v + vnn) / 2
        if (v == vnn) and v < min(vc, vn):
            d += 0.25
        vc = vn
        v = vnn
        A.append(vn)
    print(d)

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v.append(0)
vn=0
d=0
for i in range(n):
    if v[i+1]>=v[i]:#減速しない
        if v[i]-vn>t[i]:#max速度まで行かない場合
            t1=t[i] #加速時間
            d+=(vn*t1+(t1**2)/2)
        else:#max速度まで行く場合
            t1=v[i]-vn #加速時間
            t2=t[i]-t1 #等速時間
            d+=(vn*t1+(t1**2)/2)
            vn+=t1
            d+=vn*t2
    else:#減速する
        ma=(t[i]+vn+v[i+1])/2
        if ma<=v[i]:#max速度まで行かない場合
            t1=ma-vn
            t3=t[i]-t1
            d+=(vn*t1+(t1**2)/2)
            vn+=t1
            d+=(vn*t3)-(t3**2)/2
            vn-=t3
        else:#max速度まで行く場合
            t3=v[i]-v[i+1] #減速時間
            t1=v[i]-vn #加速時間
            t2=t[i]-t1-t3 #等速時間
            d+=(vn*t1)+(t1**2)/2
            vn+=t1
            d+=vn*t2
            d+=(vn*t3)-(t3**2)/2
            vn-=t3
print(d)

Submission status: Wrong Answer

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

vel = [0]
for i in range(N):
    v = min(Velocity[i], vel[-1] + Time[i], Velocity[i + 1])
    vel.append(v)
vel[-1] = 0

ans = 0
for i in range(N):
    dist = 0
    vs = vel[i]
    vt = vel[i + 1]
    v_limit = Velocity[i]
    time = Time[i]

    if vs > vt:  # 常にvs<vtにしたい
        vs, vt = vt, vs
    dist += vs * time
    dt = vt - vs
    time = max(0, time - dt)
    dist += 0.5 * dt ** 2
    dist += time * dt

    # 左右対称の台形っぽい形の面積を求める
    t_base = time
    height = min(t_base * 0.5, v_limit - vt)
    t_top = max(0, t_base - 2 * height)
    dist += (t_base + t_top) * height * 0.5

    ans += dist

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
ST = [0]*(N+1)
for i in range(1,N+1):
    ST[i] = ST[i-1] + T[i-1]
done = [False]*N
def rec(st, gt, v, idx):
    done[idx] = True
    # print(st, gt, v, idx)
    dis = gt - st
    mx = dis/2+v
    if mx <= V[idx]:
        return (v+mx)/2*dis
    tot = 0
    dt = V[idx] - v
    tot += V[idx]*max(0, min(gt-dt, ST[idx+1])-max(st+dt, ST[idx]))
    # print("before st", tot)
    # st ~ ST[idx]
    tot += (v+V[idx])/2*dt
    # print("before2 st", (v+V[idx])/2*dt)
    if idx-1 >= 0 and st+dt < ST[idx]:
        mi = idx-1
        for i in range(0, idx):
            if st+dt < ST[i+1] and V[i] < V[mi]:
                mi = i
        if not done[mi]:
            tot += rec(st+dt, ST[idx], V[idx], mi)
    # ST[idx] ~ gt
    tot += (v+V[idx])/2*dt
    # print("before2 gt", (v+V[idx])/2*dt)
    if idx+1 <= N-1 and gt-dt > ST[idx+1]:
        mi = idx+1
        for i in range(idx+1, N):
            if gt-dt > ST[i] and V[i] < V[mi]:
                mi = i
        if not done[mi]:
            tot += rec(ST[idx+1], gt-dt, V[idx], mi)
    # print("finish gt", tot)
    return tot

mi = 0
for i in range(N):
    if V[i] < V[mi]:
        mi = i
print(rec(0, ST[N], 0, mi))

Submission status: Wrong Answer

Solution code:
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
ST = [0]*(N+1)
for i in range(1,N+1):
    ST[i] = ST[i-1] + T[i-1]
done = [False]*N
def rec(st, gt, v, idx):
    done[idx] = True
    print(st, gt, v, idx)
    dis = gt - st
    mx = dis/2+v
    if mx <= V[idx]:
        return (v+mx)/2*dis
    tot = 0
    dt = V[idx] - v
    tot += V[idx]*max(0, min(gt-dt, ST[idx+1])-max(st+dt, ST[idx]))
    # print("before st", tot)
    # st ~ ST[idx]
    tot += (v+V[idx])/2*dt
    # print("before2 st", (v+V[idx])/2*dt)
    if idx-1 >= 0 and st+dt < ST[idx]:
        mi = idx-1
        for i in range(0, idx):
            if st+dt < ST[i+1] and V[i] < V[mi]:
                mi = i
        if not done[mi]:
            tot += rec(st+dt, ST[idx], V[idx], mi)
    # ST[idx] ~ gt
    tot += (v+V[idx])/2*dt
    # print("before2 gt", (v+V[idx])/2*dt)
    if idx+1 <= N-1 and gt-dt > ST[idx+1]:
        mi = idx+1
        for i in range(idx+1, N):
            if gt-dt > ST[i] and V[i] < V[mi]:
                mi = i
        if not done[mi]:
            tot += rec(ST[idx+1], gt-dt, V[idx], mi)
    # print("finish gt", tot)
    return tot

mi = 0
for i in range(N):
    if V[i] < V[mi]:
        mi = i
print(rec(0, ST[N], 0, mi))

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v.append(0)
vn=0
d=0
for i in range(n):
    if v[i+1]>=v[i]:#減速しない
        if v[i]-vn>t[i]:#max速度まで行かない場合
            t1=t[i] #加速時間
            d+=(vn*t1+(t1**2)/2)
        else:#max速度まで行く場合
            t1=v[i]-vn #加速時間
            t2=t[i]-t1 #等速時間
            d+=(vn*t1+(t1**2)/2)
            vn+=t1
            d+=vn*t2
    else:#減速する
        ma=(t[i]+vn+v[i+1])/2
        if ma<v[i]:#max速度まで行かない場合
            t1=ma-vn
            t3=t[i]-t1
            d+=(vn*t1+(t1**2)/2)
            vn+=t1
            d+=(vn*t3)-(t3**2)/2
            vn-=t3
        else:#max速度まで行く場合
            t3=v[i]-v[i+1] #減速時間
            t1=v[i]-vn #加速時間
            t2=t[i]-t1-t3 #等速時間
            d+=(vn*t1)+(t1**2)/2
            vn+=t1
            d+=vn*t2
            d+=(vn*t3)-(t3**2)/2
            vn-=t3
print(d)

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v.append(0)
vn=0
d=0
for i in range(n):
    if v[i+1]>=v[i]>=vn:#減速しない
        if v[i]-vn>t[i]:#max速度まで行かない場合
            t1=t[i] #加速時間
            d+=(vn*t1+(t1**2)/2)
        else:#max速度まで行く場合
            t1=v[i]-vn #加速時間
            t2=t[i]-t1 #等速時間
            d+=(vn*t1+(t1**2)/2)
            vn+=t1
            d+=vn*t2
    else:#減速する
        ma=(t[i]+vn+v[i+1])/2
        if ma<v[i]:#max速度まで行かない場合
            t1=ma-vn
            t3=t[i]-t1
            d+=(vn*t1+(t1**2)/2)
            vn+=t1
            d+=(vn*t3)-(t3**2)/2
            vn-=t3
        else:#max速度まで行く場合
            t3=v[i]-v[i+1] #減速時間
            t1=v[i]-vn #加速時間
            t2=t[i]-t1-t3 #等速時間
            d+=(vn*t1)+(t1**2)/2
            vn+=t1
            d+=vn*t2
            d+=(vn*t3)-(t3**2)/2
            vn-=t3
print(d)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

max_speed_from_left = [0] * (N + 1)
max_speed_from_right = [0] * (N + 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) / 2
        x = t
    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: Wrong Answer

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

s = [0] * (n + 1)

for i in range(1, n):
    s[i] = min(v[i-1], v[i])

update = True

while update:
    update = False

    for i in range(n-1):
        if s[i+1] >= s[i]:
            if s[i+1] > s[i] + t[i]:
                s[i+1] = s[i] + t[i]
                update = True
        else:
            if s[i+1] < s[i] - t[i]:
                s[i+1] = s[i] - t[i]
                update = True

    for i in range(n-1, 0, -1):
        if s[i] >= s[i+1]:
            if s[i] > s[i+1] + t[i]:
                s[i] = s[i+1] + t[i]
                update = True
        else:
            if s[i] < s[i+1] - t[i]:
                s[i] = s[i+1] - t[i]
                update = True

distance = 0
for i in range(n):
    high = (t[i] + s[i] + s[i+1]) / 2
    if high <= v[i]:
        distance += (high - s[i]) * (s[i] + high) / 2 +\
                    (t[i] - high + s[i]) * (high + s[i+1]) / 2
    else:
        distance += (v[i] - s[i]) * (s[i] + v[i]) / 2 +\
                    (v[i] - s[i+1]) * (s[i+1] + v[i]) / 2 +\
                    (t[i] - 2 * v[i] + s[i] + s[i+1]) * v[i]

print(distance)

Submission status: Wrong Answer

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

s = [0] * (n + 1)

for i in range(1, n):
    s[i] = min(v[i-1], v[i])

update = True

while update:
    update = False

    for i in range(n):
        if s[i+1] >= s[i]:
            if s[i+1] > s[i] + t[i]:
                s[i+1] = s[i] + t[i]
                update = True
        else:
            if s[i+1] < s[i] - t[i]:
                s[i+1] = s[i] - t[i]
                update = True

distance = 0
for i in range(n):
    high = (t[i] + s[i] + s[i+1]) / 2
    if high <= v[i]:
        distance += (high - s[i]) * (s[i] + high) / 2 +\
                    (t[i] - high + s[i]) * (high + s[i+1]) / 2
    else:
        distance += (v[i] - s[i]) * (s[i] + v[i]) / 2 +\
                    (v[i] - s[i+1]) * (s[i+1] + v[i]) / 2 +\
                    (t[i] - 2 * v[i] + s[i] + s[i+1]) * v[i]

print(distance)

Submission status: Wrong Answer

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

ans = 0
v_p = [0]
for i in range(N - 1):
    ans_tmp = 0
    if v[i] > v_p[-1]:
        v_tmp = min(v_p[-1] + t[i], v[i])
        if v_tmp == v[i]:
            ans_tmp += v[i] * t[i]
            ans_tmp -= (v[i] - v_p[-1]) * (v[i] - v_p[-1]) / 2
        else:
            ans_tmp += v_tmp * v_tmp // 2
    else:
        v_tmp = max(v_p[-1] - t[i], v[i])
        if v_tmp == v[i]:
            ans_tmp += v[i] * t[i]
            ans_tmp += (v_p[-1] - v[i]) * (v_p[-1] - v[i]) / 2
        else:
            ans_tmp += v[i] * t[i]
            ans_tmp += (v_p[-1] - v_tmp) * (v_p[-1] - v_tmp) / 2
    #
    print("#", i, v_p[-1], (t[i], v[i]), v_tmp)
    v_p.append(v_tmp)
    ans += ans_tmp
else:
    if 2 * v[-1] - v_p[-1] <= t[-1]:
        ans += v[-1] * t[-1]
        ans -= (v[-1] - v_p[-1]) * (v[-1] - v_p[-1]) / 2
        ans -= v[-1] * v[-1] / 2
    else:
        v_max = (v_p[-1] + t[-1]) / 2
        ans -= (v_max - v_p[-1]) * (v_max - v_p[-1]) / 2
        ans -= v_max * v_max / 2

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
end = [-1]*N
end[-1] = 0

for i in range(N-2, -1, -1):
    end[i] = min(end[i+1]+t[i+1], v[i], v[i+1])

ans = 0
s = 0

for i in range(N):
    e = end[i]

    if s+t[i]<=e:
        ans += (s+e)*t[i]/2
        s = s+t[i]
    else:
        up = min(v[i], (s+e+t[i])/2)
        ans += (s+up)*(up-s)/2
        ans += (e+up)*(up-e)/2
        ans += up*(t[i]-(up-s)-(up-e))
        s = e

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
u=list(map(int,input().split()))
speed=[0]
for i in range(n):
  speed+=[u[i]]*t[i]*2
m=len(speed)
speed[0]=0
speed[-1]=0
for i in range(1,m):
  speed[i]=min(speed[i],speed[i-1]+0.5)
for i in range(m-2,-1,-1):
  speed[i]=min(speed[i],speed[i+1]+0.5)
ans=0
for i in range(1,m):
  ans+=min(speed[i-1],speed[i])*0.5
  ans+=abs(speed[i-1]-speed[i])*0.25
print(ans)

Submission status: Wrong Answer

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

l = sum(T) * 2 + 1
t_cond = [0] + T + [l // 2]
v_cond = [0] + V + [0]
memo = [[0] * l for _ in range(N + 2)]
left = 0
for i in range(N + 2):
    for j in range(l):
        if j < left:
            memo[i][j] = v_cond[i] + (left - j)
        elif left <= j <= left + t_cond[i] * 2:
            memo[i][j] = v_cond[i]
        else:
            memo[i][j] = v_cond[i] + (j - left - t_cond[i] * 2)
            
    # Shift lower bound
    left += t_cond[i] * 2

f = [min(memo[i][j] for i in range(N + 2)) for j in range(l)]
ans = 0
for i in range(l - 1):
    ans += 0.25 * (f[i] + f[i + 1])
print(ans / 2)

Submission status: Wrong Answer

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

v_left_list=[0]
for i in range(N):
  v_left=min(vlist[i],v_left_list[-1]+tlist[i],vlist[i+1]+tlist[i])
  v_left_list.append(v_left)
v_left_list.append(0)
#print(v_left_list)

v_right_list=[0]
for i in reversed(range(N)):
  v_right=min(vlist[i],v_right_list[-1]+tlist[i],vlist[i]+tlist[i])
  v_right_list.append(v_right)
v_right_list.append(0)
v_right_list=v_right_list[::-1]
#print(v_right_list)

vlist=[]
for i in range(N+2):
  vlist.append(min(v_left_list[i],v_right_list[i]))
#print(vlist)

answer=0
v_now=0
for i in range(1,N+1):
  v_start=v_now
  v_max=vlist[i]
  v_end=vlist[i+1]
  #print(v_start,v_max,v_end)
  
  if v_max>v_now:
    t1=v_max-v_now
  else:
    t1=0
  if v_max>v_end:
    t3=v_max-v_end
  else:
    t3=0
  t2=tlist[i-1]-t1-t3  
  
  answer_i=0
  if t2>=0:
    #print(t1,t2,t3)
    answer_i+=(v_now+v_max)*t1/2
    answer_i+=v_max*t2
    answer_i+=(v_max+v_end)*t3/2
  else:
    t3=(v_now+t1-v_end)/2
    t2=0
    t1=tlist[i-1]-t3
    #print(t1,t2,t3)
    answer_i+=(2*v_now+t1)*t1/2
    answer_i+=(2*v_end+t3)*t3/2
  
  answer+=answer_i
  v_now=min(v_max,v_end)
  
print(answer)

Submission status: Wrong Answer

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

dp = [[-1]*102 for _ in range(sum(T) + 1)]
dp[0][0] = 0

nt = 0
pt = T[0]
p = 200
# 配る
delta = [-1,0,1]
for i in range(sum(T)):
    if pt == i:
        p = V[nt]
        nt += 1
        pt += T[nt]
    for j in range(101):
        if j > p or j > V[nt] or dp[i][j] == -1:break
        for d in delta:
            nj = j + d
            if 0 <= nj:
                if d != 0 or p == j or j == V[nt]:
                    dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + (j+nj)/2)
                else :
                    dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + j + 0.25)
    p = 200
print(dp[-1][0])

Submission status: Wrong Answer

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

N = int(input())
t = list(map(int, input().split())) + [0]
v = list(map(int, input().split())) + [0]
v0 = 0
ans = 0
for i in range(N):
    t1, v1 = t[i], v[i]
    time = t1
    v_max = float('inf')
    for t2, v2 in zip(t[i+1:], v[i+1:]):
        if v2 < v_max:
            v_max = min(v_max, (time + v0 + v2) / 2)
        time += t2

    if v_max > v0 + t1:
        s1 = v1 - v0
        if s1 < t1:
            ans += (v0 + v1) * s1 / 2 + v1 * (t1 - s1)
            v0 = v1
        else:
            ans += (v0 + v0 + t1) * t1 / 2
            v0 = v0 + t1
    else:
        v1 = min(v1, v_max)
        s1 = v1 - v0
        s2 = v1 - (v_max - (t1 - (v_max - v0)))
        v2 = v1 - s2
        ans += (v0 + v1) * s1 / 2 + (t1 - s1 - s2) * v1 + (v2 + v1) * s2 / 2
        v0 = v2
print(ans)

Submission status: Wrong Answer

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

N = int(input())
t = list(map(int, input().split())) + [0]
v = list(map(int, input().split())) + [0]
v0 = 0
ans = 0
for i in range(N):
    t1, v1 = t[i], v[i]
    time = t1
    v_max = float('inf')
    for t2, v2 in zip(t[i+1:], v[i+1:]):
        if v2 < v_max:
            v_max = min(v_max, (time + v0 + v2) / 2)
        time += t2

    if v_max <= v1:
        s1 = v_max - v0
        s2 = t1 - s1
        v2 = v_max - s2
        ans += (v0 + v_max) * s1 / 2 + (v2 + v_max) * s2 / 2
        v0 = v2
    else:
        if v_max > v0 + t1:
            s1 = v1 - v0
            if s1 < t1:
                ans += (v0 + v1) * s1 / 2 + v1 * (t1 - s1)
                v0 = v1
            else:
                ans += (v0 + v0 + t1) * t1 / 2
                v0 = v0 + t1
        else:
            s1 = v1 - v0
            s2 = v1 - (v_max - (t1 - (v_max - v0)))
            v2 = v1 - s2
            ans += (v0 + v1) * s1 / 2 + (t1 - s1 - s2) * v1 + (v2 + v1) * s2 / 2
            v0 = v2
print(ans)

Submission status: Wrong Answer

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

unit = 1000

acumT = [0] * (n + 1)
for i in range(n):
  acumT[i+1] = acumT[i] + T[i]
  
PV = [0] * (sum(T) * unit + 1)
for (t1, t2), (v1, v2, v3) in zip(zip(acumT, acumT[1:]), zip(V, V[1:], V[2:])):
  for i in range(t1 * unit, t2 * unit + 1):
    ii = i / unit 
    PV[i] = min(ii, -ii + sum(T), v2, ii - t1 + v1, -ii + t2 + v3)

area = sum((i + j) / unit / 2 for i, j in zip(PV, PV[1:]))  
print(area)