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, os

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

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


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

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

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

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

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

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


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


    



solve()

Submission status: Wrong Answer

Solution code:
import sys, os

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

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


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

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

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

    vs[sumt] = 0
    for i in range(sumt-1, 0, -1):
        vs[i] = min(vs[i+1]+1, vs[i])

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



    print(ans)
    


    



solve()

Submission status: Wrong Answer

Solution code:
import sys, os

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

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


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

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

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

    vs[sumt] = 0
    for i in range(sumt-1, 0, -1):
        vs[i] = min(vs[i+1]+1, vs[i])

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


    print(vs)
    print(ans)
    


    



solve()

Submission status: Wrong Answer

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


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

    limit = np.zeros((t_period[N]+1,))
    for i in range(1, N):
        limit[t_period[i]] = min((V[i-1], V[i]))
    for i in range(N):
        limit[t_period[i]+1:t_period[i+1]] = V[i]
    
    speed = np.zeros((t_period[N]+1,))

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

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

    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

now_v = 0

for i in range(N):
    if v[i] > now_v + t[i]:
        v[i] = now_v + t[i]

    now_v = v[i]

now_v = 0
for i in range(1, N + 1):
    if v[N - i] > now_v + t[N - i]:
        v[N - i] = now_v + t[N - i]

    now_v = v[N - i]


def f(v0, v1, v2, t, i):
    if v0 <= v1 <= v2:
        if v1 - v0 < t:
            return 0.5 * (v1**2 - v0**2) + v1 * (t - v1 + v0)
        else:
            return 0.5 * (t ** 2) + v0 * t
    elif v0 >= v1 <= v2:
        return v1 * t
    elif v0 <= v1 > v2:
        if v1 - v0 + v1 - v2 > t:
            v11 = 0.5 * (t - abs(v0 - v2)) + max(v0, v2)
            v[i] = v2
            return 0.5 * (v11**2-v0**2) + 0.5 * (v11**2-v2**2)
        else:
            t -= v1-v0 + v1-v2
            return 0.5 * (v1**2-v0**2) + 0.5 * (v1**2-v2**2) + t * v1
    else:
        return 0.5 * (v0**2 - v1**2) + v0 * (t - v0 + v1)


v.append(0)
d = f(0, v[0], v[1], t[0], 0)
for i in range(1, N):
    d += f(v[i-1], v[i], v[i+1], t[i], i)

print(d)

Submission status: Wrong Answer

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

t_cnt = 0
for t, v in zip(ts, vs):
    for j in range(t+1):
        max_v[t_cnt + j] = min(max_v[t_cnt + j], v)

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

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

Submission status: Wrong Answer

Solution code:

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

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

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

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

ans = 0
for i in range(n):
    ti = t[i]
    vi = v[i]
    mi = maxspeed[i]
    mi1= maxspeed[i+1]
    ta = vi - mi
    tb = vi - mi1
#    print(ta,tb,ti)
    if ta + tb <= ti:
        c = (mi+vi)*ta/2 + vi*(ti-ta-tb) + (mi1+vi)*tb/2
    else:
        a = (mi1+ti-mi)/2
        c = (mi+mi+a)*a/2 + (mi+a+mi1)*(ti-a)/2
#    print(c)
    ans += c

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ts = [int(item) 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 += 1

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

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

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

print(ans + sum(speed_r))

Submission status: Wrong Answer

Solution code:
n = int(input())
ts = [int(item) 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 += 1

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

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

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

print(ans + sum(speed_r))

Submission status: Wrong Answer

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


times = [0]
suma = 0
for i in range(n):
    suma += t[i]*2
    times.append(suma)

limits = [0 for i in range(suma)]

#vによる制限を記述
for i in range(n):
    for k in range(times[i],times[i+1]):
        limits[k] = v[i+1]


for i in range(n):
    for k in range(times[i+1]):
        limits[k] = min(limits[k],v[i+2]+0.5*(times[i+1]-k))

for i in range(n):
    for k in range(times[i],times[i+1]):
        limits[k] = min(limits[k],v[i]+(k-times[i])*0.5)


limits = limits + [0]


#print(limits)

ans = 0
for i in range(len(limits)-1):
    ans += (limits[i]+limits[i+1])/2
print(ans/2)

Submission status: Wrong Answer

Solution code:
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
dp=[0]*(N+1)
for i in range(1,N):
    dp[i]=min(V[i],V[i-1],T[i-1]+dp[i-1])
for j in range(N-1,0,-1):
    dp[i]=min(dp[i],dp[i+1]+T[i])
dist=0
for i in range(N):
    inc=V[i]-dp[i]
    dec=T[i]-V[i]+dp[i+1]
    if inc<=dec:
        dist+=0.5*inc*(V[i]+dp[i])+(dec-inc)*V[i]+0.5*(T[i]-dec)*(V[i]+dp[i+1])
    elif dec<inc:
        switch=(dp[i+1]-dp[i]+T[i])/2
        Vmax=dp[i]+switch
        dist+=0.5*(switch*(Vmax+dp[i])+(T[i]-switch)*(Vmax+dp[i+1]))
print(dist)

Submission status: Wrong Answer

Solution code:
N=int(input())

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

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

T=0
s=0.0
i=0
d=0.0
j=0
while T<t[-1]:
    d+=s
    T+=1
    if(s>=(last[j][0]+1-T)+last[j][1]):
        if(s-int(s)==0):
            s-=1
        else:
            s-=(s-int(s))
    elif(s<v[i]):
        s+=min(1.0,v[i]-s)

    if(T==last[j][0]):
        j+=1
    try:
        if(T==t[i]):
            i+=1
    except:
        pass

print(d)

Submission status: Wrong Answer

Solution code:
def atcoder_express(N: int, T: list, V: list)->float:
    '''V の上限を補正する。
    1. 次の時間帯の速度上限が今の時間帯のそれ以上なら変更なし。
    2. 次の時間帯の速度上限が今の時間帯のそれより小さい場合、減
    速時間を確保しないといけない。具体的には、次の時間帯の速度上
    限を `vn` 、現在の時間帯のそれを `vc` とすると、
    `t > |vc-vn|` なら `vc` に、そうでないなら、 `t + vn` 
    に変更する。

    これは次の時間帯の速度上限が補正されてないと二度手間になるの
    で後ろから決めていく。あとは前方から順番に各時間帯内で、「前
    の時間帯の速度->現在の時間帯の速度->次の時間帯の速度」となる
    ようにして速度グラフの面積を求めていくだけ。
    '''
    # 速度上限の補正
    vn = 0  # 次の時間帯の速度上限
    for i in range(N-1, -1, -1):
        t, vc = T[i], V[i]
        if vc > vn and t < vc - vn:
            V[i] = t + vn
        vn = vc

    # 扱いやすいように、最後の速度が 0 になることを追記しておく。
    V.append(0)

    # 各時間帯の速度面積を求める。
    vp = 0  # 前の時間帯の最終速度
    total = 0.0
    for i in range(N):
        t, vc, vn = T[i], V[i], V[i+1]
        # print('>>', t, vp, vc, vn)
        if vc > vn:
            # vc > vn の場合は減速する必要がある。
            # 前述の速度補正によって、減速時間は確実
            # に確保できる。
            tn = vc - vn
            if vp < vc:
                # hoge
                tp = vc - vp

                if t < tn + tp:
                    # 加速時間が足りない場合は最大
                    # 速度を補正する。
                    # 以下の式より求まる。
                    # tn + tp = t
                    # tn = vc - vn
                    # tp = vc - vp
                    # ∴ vc = (t + vn + vp) / 2
                    vc = (t + vn + vp) / 2
                    tn = vc - vn
                    tp = vc - vp
            else:
                # vp == vc が保障される。
                # 前述の速度補正によって、減速時間は確実
                # に確保できるので、その他の補正はいらない
                tp = 0
        else:
            # vc > vn で場合は出来るだけ加速して
            # vc の時間を長く確保する。
            vc = min(vc, t + vp)
            tn = 0
            tp = vc - vp
            pass

        # 残った時間が vc でいられる時間
        tc = max(0, t-tp-tn)
        # print(i, (tp, vp), (tc, vc), (tn, vn))
        total += (vp + vc) * tp / 2
        total += vc * tc
        total += (vc + vn) * tn / 2
        vp = vp + tp - tn

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

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split())) + [0]

    cv = 0
    dist = 0
    for i in range(N):
        t, v, nv = 10 * T[i], V[i], V[i+1]
        for ct in range(0, t, 5):
            if cv - nv - (t - ct)/10 >= 0:
                dist += (cv - 0.125) / 2
                cv -= 0.5

            elif cv < v:
                dist += (cv + 0.125) / 2
                cv += 0.5

            else:
                dist += cv / 2
            
    print(dist)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split())) + [0]

    cv = 0
    dist = 0
    for i in range(N):
        t, v, nv = 10 * T[i], V[i], V[i+1]
        for ct in range(0, t, 5):
            if cv - nv - (t - ct) >= 0:
                dist += cv - 0.25
                cv -= 0.5

            elif cv < v:
                dist += cv + 0.25
                cv += 0.5

            else:
                dist += cv
            
    print(dist)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split())) + [0]

    cv = 0
    dist = 0
    for i in range(N):
        t, v, nv = 10 * T[i], 10 * V[i], 10 * V[i+1]
        for ct in range(0, t, 5):
            if cv - nv - (t - ct) >= 0:
                dist += cv - 12.5
                cv -= 5

            elif cv < v:
                dist += cv + 12.5
                cv += 5

            else:
                dist += cv
            
    print(dist/20)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)

print(t)
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: Wrong Answer

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 = v_max - v_start
    kouten_t_limit2 = v_end + dt - v_max
    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)

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

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]):
            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/4)


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

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

vstarts = [0] * (N + 1)
X = [0] * N
i = 0
while i != N:
    vstart = vstarts[i]
    if i != N - 1:
        vmax = V[i]
        vend = V[i + 1]
    else:
        vmax = V[i]
        vend = 0

    if vmax < vend:
        if vmax > vstart + T[i]:
            X[i] = (vstart + vstart + T[i]) * T[i] / 2
            vstarts[i + 1] = vstart + T[i]
        else:
            X[i] = vmax * T[i] - (vmax - vstart) ** 2 / 2
            vstarts[i + 1] = vmax
    else:
        if vend - vstart > T[i]:
            X[i] = (vstart + vstart + T[i]) * T[i] / 2
            vstarts[i + 1] = vstart + T[i]

        elif vstart - vend > T[i]:
            V[i] = vend + T[i]
            i = i - 1
            continue

        elif 2 * vmax - vstart - vend < T[i]:
            X[i] = vmax * T[i] - (vmax - vstart) ** 2 / 2 - (vmax - vend) ** 2 / 2
        else:
            vmax = (T[i] + vstart + vend) / 2
            X[i] = vmax * T[i] - (vmax - vstart) ** 2 / 2 - (vmax - vend) ** 2 / 2
        vstarts[i + 1] = vend

    i += 1

print(sum(X))

Submission status: Wrong Answer

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

vstart = 0
X = [0] * N
i = 0
while i != N:
    if i != N - 1:
        vmax = V[i]
        vend = V[i + 1]
    else:
        vmax = V[i]
        vend = 0

    if vmax < vend:
        if vmax > vstart + T[i]:
            X[i] = (vstart + vstart + T[i]) * T[i] / 2
            vstart = vstart + T[i]
        else:
            X[i] = vmax * T[i] - (vmax - vstart) ** 2 / 2
            vstart = vmax
    else:
        if vend - vstart > T[i]:
            X[i] = (vstart + vstart + T[i]) * T[i] / 2
            vstart = vstart + T[i]
        elif vstart - vend > T[i]:
            V[i] = vend + T[i]
            i = i - 1
            continue

        elif 2 * vmax - vstart - vend < T[i]:
            X[i] = vmax * T[i] - (vmax - vstart) ** 2 / 2 - (vmax - vend) ** 2 / 2
        else:
            vmax = (T[i] + vstart + vend) / 2
            X[i] = vmax * T[i] - (vmax - vstart) ** 2 / 2 - (vmax - vend) ** 2 / 2
        vstart = vend

    i += 1

print(sum(X))

Submission status: Wrong Answer

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

vstart = 0
x = 0
for i in range(N):
    if i != N - 1:
        vmax = V[i]
        vend = V[i + 1]
    else:
        vmax = V[i]
        vend = 0

    if vmax < vend:
        if vmax > vstart + T[i]:
            x += (vstart + vstart + T[i]) * T[i] / 2
            vstart = vstart + T[i]
        else:
            x += vmax * T[i] - (vmax - vstart) ** 2 / 2
            vstart = vmax
    else:
        if 2 * vmax - vstart - vend < T[i]:
            x += vmax * T[i] - (vmax - vstart) ** 2 / 2 - (vmax - vend) ** 2 / 2
        else:
            vmax = (T[i] + vstart + vend) / 2
            x += vmax * T[i] - (vmax - vstart) ** 2 / 2 - (vmax - vend) ** 2 / 2
        vstart = vend

print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
v0 = 0
s = [0] * n
for i in range(n):
    if i < n - 1:
        v1 = v[i + 1]
    else:
        v1 = 0
    x = max(0, min(t[i], (v1 - v0 + t[i]) / 2))
    x2 = v[i] - v0
    if x + v0 > v[i]:
        x2 = min(t[i], v1 - v[i] + t[i])
        s[i] += (v[i] + v0) * (v[i] - v0) / 2
        s[i] += (x2 - v[i] + v0) * v[i]
        s[i] += (v[i] + v1) * (t[i] - x2) / 2
    else:
        s[i] += (2 * v0 + x) * x / 2
        s[i] += (v0 + x + v1) * (t[i] - x) / 2
    v0 = min(v[i], v1, v0 + t[i])
print(sum(s))

Submission status: Wrong Answer

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

T = [0 for i in range(n)]
T[0] = t[0]
for i in range(n-1):
    T[i+1] = T[i] + t[i+1]

INF = float('inf')
V = [INF for i in range(2*T[n-1]+1)]

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

for vi in range(n):
    for ti in range(2*T[n-1]+1):
        if vi == 0:
            if ti <= T[0] * 2:
                V[ti] = min(V[ti], v[0])
            else:
                V[ti] = min(V[ti], v[0] + ti * 0.5 - T[0])
        else:
            if ti <= T[vi-1] * 2:
                V[ti] = min(V[ti], v[vi] + T[vi-1] - ti * 0.5)
            elif (T[vi-1] * 2 <= ti) and (ti <= T[vi] * 2):
                V[ti] = min(V[ti], v[vi])
            else:
                V[ti] = min(V[ti], v[vi] + (ti * 0.5 - t[vi]))

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

print(ans)

Submission status: Wrong Answer

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

T = [0 for i in range(n)]
T[0] = t[0]
for i in range(n-1):
    T[i+1] = T[i] + t[i+1]

INF = float('inf')
V = [INF for i in range(2*T[n-1]+1)]

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

for vi in range(n):
    for ti in range(2*T[n-1]+1):
        if vi == 0:
            if ti <= T[0] * 2:
                V[ti] = min(V[ti], v[0])
            else:
                V[ti] = min(V[ti], v[0] + ti * 0.5 - T[0])
        else:
            if ti <= T[vi-1] * 2:
                V[ti] = min(V[ti], v[vi] + T[vi-1] - ti * 0.5)
            elif (T[vi-1] * 2 <= ti) and (ti <= T[vi] * 2):
                V[ti] = min(V[ti], v[vi])
            else:
                V[ti] = min(V[ti], v[vi] + (ti * 0.5 - t[vi]))

ans = 0
for i in range(2*t[n-1]):
    ans += (V[i] + V[i+1]) * 0.5 * 0.5

print(ans)

Submission status: Wrong Answer

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

t_cum = []
time = 0
for i in range(n):
    time += t[i]
    t_cum.append(time)

v.append(0)

sum_t = sum(t)
V_max_list = []
V_max = v[0]
for T in range(sum_t+1):
    if 0 <= T and T <= t_cum[0]:
        V_max = v[0]
        for i in range(0, n):
            V_max = min(V_max, v[i+1] + max(0, t_cum[i] - T))
    else:
        for i in range(n-1):
            if t_cum[i] <= T and T <= t_cum[i+1]:
                V_max = v[i+1]
                for i in range(i+1, n):
                    V_max = min(V_max, v[i+1] + max(0, t_cum[i] - T))
    V_max_list.append(V_max)

v_now = 0
v_next = 0
ans = 0

for T in range(sum_t):
    if V_max_list[T+1] >= v_now + 1:
        v_next = v_now + 1
    elif V_max_list[T+1] == v_now:
        v_next = v_now
    else:
        v_next = v_now - 1
    ans += (v_now + v_next) * 0.5
    v_now = v_next

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n = ni()
t = [0] + list(li())
v = [0] + list(li()) + [0]

t_acc = list(accumulate(t))
t_max = t_acc[-1]
t_cur = [10**10]*(2*t_max+1)

interval = dict({(0,0): 0, (t_max,t_max): 0})
for i in range(n):
    interval.update({(t_acc[i], t_acc[i+1]): v[i+1]})
    
for t_idx in range(2*t_max+1):
    for i, ((tl,tr), v) in enumerate(interval.items()):
        
        if t_idx*0.5 < tl:
            t_cur[t_idx] = min(t_cur[t_idx], abs(v+(tl-t_idx*0.5)))
            
        elif tl <= t_idx*0.5 <= tr:
            t_cur[t_idx] = min(t_cur[t_idx], v)
            
        elif tr < t_idx*0.5:
            t_cur[t_idx] = min(t_cur[t_idx], abs(v+(t_idx*0.5-tr)))

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

print(int(ans))

Submission status: Wrong Answer

Solution code:
# ABC 076 D

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

e = sum(t)*2
vmax = [0 for k in range(e+2)]

s = 0
for k in range(N):
    for l in range(1,t[k]*2+1):
        vmax[s+l] = v[k]
    s += t[k]*2

s = 0
for k in range(N-1):
    for l in range(1,t[k]*2+1):
        vmax[s+l]= max(0,min(vmax[s+l],v[k+1]+t[k]-l/2))
    s += t[k]*2

for k in range(e+1):
    vmax[k] = min(vmax[k],e/2-k/2)

t = 0
hayasa = 0
ans = 0
for k in range(1,e+1):
    t = hayasa 
    if hayasa < vmax[k]:
        hayasa += 0.5
    elif hayasa > vmax[k]:
        hayasa -= 0.5
    ans += (t+hayasa)/4

print(ans)

Submission status: Wrong Answer

Solution code:
# ABC 076 D

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

e = sum(t)*2
vmax = [0 for k in range(e+2)]

s = 0
for k in range(N):
    for l in range(1,t[k]*2+1):
        vmax[s+l] = v[k]
    s += t[k]*2

s = 0
for k in range(N-1):
    for l in range(1,t[k]*2+1):
        vmax[s+l]= min(vmax[s+l],v[k+1]+t[k]-l/2)
    s += t[k]*2

for k in range(e+1):
    vmax[k] = min(vmax[k],e/2-k/2)

t = 0
hayasa = 0
ans = 0
for k in range(1,e+1):
    t = hayasa 
    if hayasa < vmax[k]:
        hayasa += 0.5
    elif hayasa > vmax[k]:
        hayasa -= 0.5
    ans += (t+hayasa)/4

print(ans)

Submission status: Wrong Answer

Solution code:
# ABC 076 D

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

e = sum(t)*2
vmax = [0 for k in range(e+1)]

s = 0
for k in range(N):
    for l in range(t[k]*2):
        vmax[s+l] = v[k]
    s += t[k]*2

for k in range(e+1):
    vmax[k] = min(vmax[k],e/2-k/2)

s = 0
for k in range(N-1):
    for l in range(t[k]*2):
        vmax[s+l]= min(vmax[s+l],v[k+1]+t[k]-l/2)
    s += t[k]*2

hayasa = 0
ans = 0
for k in range(1,e+1):
    t = hayasa
    if hayasa < vmax[k-1]:
        hayasa += 0.5
    elif hayasa > vmax[k]:
        hayasa -= 0.5
    ans += (t+hayasa)/4

print(ans)