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:
n = int(input())
time = list(map(int, input().split())) + [0]
vels = list(map(int, input().split())) + [0]
for i in range(n)[::-1]:
    if vels[i+1] < vels[i]:
        vels[i] = min(vels[i+1] + time[i], vels[i])

ans = 0
vnow = 0
for i in range(n):
    if vels[i] <= vels[i+1]:
        acc_time =  min(vels[i] - vnow, time[i])
        ans += acc_time**2 / 2 + vnow * acc_time
        # print(ans, vnow)
        vnow = vnow + acc_time
        ans += (time[i]-acc_time) * vnow
        # print(ans, vnow, acc_time)
    else:
        deacc_time = vnow - vels[i+1]
        res_time = time[i] - deacc_time
        # up and down
        acc_time =  min((vels[i] - vnow) * 2, res_time) / 2
        ans += (acc_time**2 / 2 + vnow * acc_time)
        ans += (res_time-acc_time * 2) * (vnow + acc_time)
        ans += (-acc_time**2 / 2 + (vnow + acc_time) * acc_time)
        # down
        ans += -deacc_time**2 / 2 + vnow * deacc_time
        vnow = vnow - deacc_time
        # print(vnow, acc_time, res_time, deacc_time)
    # print(ans)
# print(vels)
print('{:.6f}'.format(ans))

Submission status: Wrong Answer

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

ans = 0
vnow = 0
for i in range(n):
    if vels[i] <= vels[i+1]:
        acc_time =  min(vels[i] - vnow, time[i])
        ans += acc_time**2 / 2 + vnow * acc_time
        # print(ans, vnow)
        vnow = vnow + acc_time
        ans += (time[i]-acc_time) * vnow
        # print(ans, vnow, acc_time)
    else:
        deacc_time = vnow - vels[i+1]
        res_time = time[i] - deacc_time
        # up and down
        acc_time =  min((vels[i] - vnow) * 2, res_time) / 2
        ans += (acc_time**2 / 2 + vnow * acc_time)
        ans += (res_time-acc_time * 2) * (vnow + acc_time)
        ans += (-acc_time**2 / 2 + (vnow + acc_time) * acc_time)
        # down
        ans += -deacc_time**2 / 2 + vnow * deacc_time
        vnow = vnow - deacc_time
        # print(vnow, acc_time, res_time, deacc_time)
    # print(ans)

print('{:.6f}'.format(ans))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate as ac
n=int(input())+2
t=[0]+list(map(int,input().split()))+[0]
v=[0]+list(map(int,input().split()))+[0]
s=[0]+list(ac(t))
def f(i,x):
    if s[i]<=x<=s[i]+t[i]:return v[i]
    elif x<s[i]:return v[i]+s[i]-x
    else:return v[i]+x-s[i]
c=float("INF")
for i in range(n):
    c=min(c,f(i,0))
e=0
for i in range(1,2*s[-1]+1):
    i=i/2
    d=float("INF")
    for j in range(n):
        d=min(d,f(j,i))
    e+=0.25*(c+d)
    c=d
print(e)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import bisect


n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
v.append(0)
t = [0]+t
t = list(accumulate(t))

a = [0]

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

print(sum(a)/2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

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

Submission status: Wrong Answer

Solution code:

n = int(input())
t_list = [ int(v) for v in input().split() ]
v_list = [ int(v) for v in input().split() ]

limit_list = [0]
for i in range(n):
    for j in range(t_list[i]):
        if v_list[i] < limit_list[-1]:
            limit_list[-1] = v_list[i]
        limit_list.append(v_list[i])
        
limit_list[-1] = 0
velocity_list = [ 0 for i in range(len(limit_list)) ]



for i in range(max(v_list)+10):
    new_velocity_list = [ j for j in velocity_list ]
    for j in range(1,len(velocity_list)-1):
        if velocity_list[j-1] == velocity_list[j] and velocity_list[j+1] == velocity_list[j] and limit_list[j] > velocity_list[j]:
            new_velocity_list[j] = velocity_list[j] + 1
    velocity_list = new_velocity_list


s = 0
for i in range(1,len(velocity_list)):
    s += (velocity_list[i-1] + velocity_list[i])/2
    if velocity_list[i-1] == velocity_list[i] and limit_list[i] > velocity_list[i]:
        s += 0.25
print(s)

Submission status: Wrong Answer

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

fMax = [0 for _ in range(20001)]
rMax = [0 for _ in range(20001)]

i    = 1
it   = 0
sm   = 0
maxV = 0

while True:
    if sm < i:
        if it == N: break
        sm += T[it]
        maxV = V[it]
        it += 1
    fMax[i] = min(fMax[i-1]+1, maxV)
    i += 1

tmpsm = 0
i     = 1
it    = 0

while True:
    if tmpsm < i:
        if it == N: break
        tmpsm += T[N-it-1]
        maxV = V[N-it-1]
        it += 1
    rMax[sm-i] = min(rMax[sm-i+1]+1, maxV)
    i += 1

ans = 0
cross = 0

for t in range(sm):
    if fMax[t] == rMax[t+1] and rMax[t] == fMax[t+1] and abs(fMax[t]-fMax[t+1]) == 1: cross += 1
    ans += min(fMax[t], rMax[t]) + min(fMax[t+1], rMax[t+1])
print(str(ans/2.0+cross*0.25))

Submission status: Wrong Answer

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

prev = 0
ans = 0
for i in range(N):
    at = 0
    if prev < V[i]:
        at = V[i] - prev
    bt = 0
    if V[i] > V[i+1]:
        bt = V[i] - V[i+1]
    if at + bt <= T[i]:
        ans += at**2/2 + at*prev + V[i]*(T[i]-at-bt) + V[i]*bt - bt**2/2
    else:
        a = (T[i]-V[i+1]+prev)/2
        b = (T[i]+V[i+1]-prev)/2
        ans += prev*b + V[i+1]*a + (a**2)/2 + (b**2)/2
    #print(i, ans)
    prev = V[i] - bt

print(ans)

Submission status: Wrong Answer

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


ans = 0
t.reverse()
v.reverse()
inlim = [0 for i in range(n)]

beflim = 0
for i in range(n):
    inlim[i] = min(beflim+t[i],v[i])
    beflim = inlim[i]

t.reverse()
v.reverse()
inlim.reverse()
inlim.append(0)
speed = 0
# print(t)
# print(v)
# print(inlim)
for i in range(n):
    uplen = 0
    stilllen = 0
    downlen = 0
    if speed > inlim[i+1]:
        todown = inlim[i+1]-speed
        lest = t[i]-todown
        maxup = lest/2
        if speed + maxup <= v[i]:
            ans += speed*t[i]+lest*lest/4-todown*todown/2
            speed = inlim[i+1]
        else:
            cuttime = (speed+maxup-v[i])
            ans += speed * t[i] + lest * lest/4 - todown * todown / 2 - cuttime*cuttime
            speed = inlim[i+1]
    else:
        maxup = t[i]
        toup = inlim[i + 1] - speed
        if toup > t[i] and speed+t[i] <= v[i]:
            ans += speed*t[i]+t[i]*t[i]/2
            speed += t[i]
        elif v[i] < inlim[i+1]:
            ans += t[i]*v[i]-v[i]*v[i]/2+speed*t[i]
            speed = v[i]
        else:
            lest = t[i]-toup
            maxup = lest / 2
            if speed + maxup <= v[i]:
                ans += speed * t[i] + lest * lest/4 + toup * toup / 2
                speed = inlim[i + 1]
            else:
                cuttime = (speed + maxup - v[i])
                # print(cuttime)
                # print(lest)
                ans += speed * t[i] + lest * lest/4 - toup * toup / 2 - cuttime * cuttime
                speed = inlim[i + 1]
    # print(ans,speed)

print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

########

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

    T = sum(t)
    max_v = []

    for i in range(N):
        max_v.extend([v[i]]*t[i]*2)

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
lt=list(map(int,input().split()))+[0]
lv=list(map(int,input().split()))+[0]
ls=[]
tmp=0
for i in lt:
    tmp+=i
    ls.append(tmp)
a=[0]
s=0
t=0
k=100
for i in range(n):
    for j in range(lt[i]*k):
        t+=1
        if lv[i]*k>lv[i+1]*k and ls[i]*k-t<s-lv[i+1]*k:s-=1
        elif s<lv[i]*k:s+=1
        #t,s=fl(t),fl(s)
        a.append(s)
print(sum(a)/k**2)

Submission status: Wrong Answer

Solution code:
def fl(x):
    digits = 5
    form = '%.'+str(digits-1)+'e'
    return float((form % x))
n=int(input())
lt=list(map(int,input().split()))+[0]
lv=list(map(int,input().split()))+[0]
ls=[]
tmp=0
for i in lt:
    tmp+=i
    ls.append(tmp)
a=[0]
s=0
t=0
k=100
for i in range(n):
    for j in range(lt[i]*k):
        t+=1/k
        if lv[i]>lv[i+1] and ls[i]-t<s-lv[i+1]:s-=1/k
        elif s<lv[i]:s+=1/k
        t,s=fl(t),fl(s)
        a.append(s)
print(sum(a)/k)

Submission status: Wrong Answer

Solution code:
n=int(input())
lt=list(map(int,input().split()))+[0]
lv=list(map(int,input().split()))+[0]
ls=[]
tmp=0
for i in lt:
    tmp+=i
    ls.append(tmp)
a=[0]
s=0
t=0
k=10000
for i in range(n):
    for j in range(lt[i]*k):
        t+=1/k
        if lv[i]>lv[i+1] and ls[i]-t<s-lv[i+1]:s-=1/k
        elif s<lv[i]:s+=1/k
        a.append(s)
print(sum(a)/k)

Submission status: Wrong Answer

Solution code:
n=int(input())
lt=list(map(int,input().split()))+[0]
lv=list(map(int,input().split()))+[0]
ls=[]
tmp=0
for i in lt:
    tmp+=i
    ls.append(tmp)
a=[0]
s=0
t=0
k=1000
for i in range(n):
    for j in range(lt[i]*k):
        t+=1/k
        if lv[i]>lv[i+1] and ls[i]-t<s-lv[i+1]:s-=1/k
        elif s<lv[i]:s+=1/k
        a.append(s)
print(sum(a)/k)

Submission status: Wrong Answer

Solution code:
n=int(input())
lt=list(map(int,input().split()))+[0]
lv=list(map(int,input().split()))+[0]
ls=[]
tmp=0
for i in lt:
    tmp+=i
    ls.append(tmp)
a=[0]
s=0
t=0
for i in range(n):
    for j in range(lt[i]*10000):
        t+=0.0001
        if lv[i]>lv[i+1] and ls[i]-t<s-lv[i+1]:s-=0.0001
        elif s<lv[i]:s+=0.0001
        a.append(s)
print(sum(a)/10000)

Submission status: Wrong Answer

Solution code:
n=int(input())
lt=list(map(int,input().split()))+[0]
lv=list(map(int,input().split()))+[0]
ls=[]
tmp=0
for i in lt:
    tmp+=i
    ls.append(tmp)
a=[0]
s=0
t=0
for i in range(n):
    for j in range(lt[i]*2):
        t+=0.5
        if lv[i]>lv[i+1] and ls[i]-t<s-lv[i+1]:s-=0.5
        elif s<lv[i]:s+=0.5
        a.append(s)
print(sum(a)/2)

Submission status: Wrong Answer

Solution code:
#小数になる場合に未対応
n=int(input())
lt=list(map(int,input().split()))+[0]
lv=list(map(int,input().split()))+[0]
ls=[]
tmp=0
for i in lt:
    tmp+=i
    ls.append(tmp)
a=[0]
s=0
t=0
for i in range(n):
    for j in range(lt[i]):
        t+=1
        if lv[i]>lv[i+1] and ls[i]-t<s-lv[i+1]:s-=1
        elif s<lv[i]:s+=1
        a.append(s)
print(sum(a))

Submission status: Wrong Answer

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

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

state = N
speed = 0

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

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

Submission status: Wrong Answer

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

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

state = N
speed = 0

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

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

Submission status: Wrong Answer

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

sumtime = sum(inl)

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

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

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

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

print(res)

Submission status: Wrong Answer

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

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

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

if N == 1:
  v[1] = upd(v[0], v[1], v[2], t[0])

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

print(ans)

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]

def exe(x, y, z, t):
  a = y - x
  b = y - z
  ta = 0
  tb = 0
  if x < y and y > z:
    if t < a + b:
      ta = (t + (z - x)) / 2
      tb = t - ta
      y = x + ta
    else:
      ta = a
      tb = b
  elif x < y:
    if t < a:
      ta = t
      y = x + t
    else:
      ta = a
  elif y > z:
    if t < b:
      tb = t
      y = z + t
    else:
      ta = a
  ans = t * y
  ans -= ta * (y - x) / 2
  ans -= tb * (y - z) / 2
  return ans, y

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

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]

def exe(x, y, z, t):
  a = y - x
  b = y - z
  ans = t * y
  ta = 0
  tb = 0
  if x < y and y > z:
    if t < a + b:
      ta = (t + (z - x)) / 2
      tb = t - ta
      y = x + ta
      ans = t * y
    else:
      ta = y - x
      tb = y - z
  elif x < y:
    ta = y - x
  elif y > z:
    tb = y - z
  ans -= ta * (y - x) / 2
  ans -= tb * (y - z) / 2
  return ans

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

print(ans)

Submission status: Wrong Answer

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

max_speed_from_left = [0] * (N+1) # index i = t[i],t[i+1]の間
max_speed_from_right = [0] * (N+1) # index i = t[i],t[i+1]の間

for i in range(1,N):
  start = max_speed_from_left[i-1]
  max_speed_from_left[i] = min(start + t[i], v[i], v[i+1])
  
for i in range(N-1,0,-1):
  start = max_speed_from_right[i+1]
  max_speed_from_right[i] = min(start + t[i+1], v[i], v[i+1])

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

def dist(left_speed,right_speed,t,v):
  x = (v - left_speed) + (v - right_speed)
  if x >= t:
    v = (left_speed + right_speed + t)/2
    x = t
  # 最高速度vに到達して、t-xあまる
  d = (left_speed + v) * (v-left_speed)/2
  d += v*(t-x)
  d += (right_speed + v) * (v-right_speed)/2
  return d

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

Submission status: Wrong Answer

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

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=[0]*(T+1)
from collections import deque
q=[deque() for i in range(101)]
s=0
for i in range(N):
    vmax[s]=min(vmax[s-1],v[i])
    q[vmax[s]].append(s)
    for j in range(t[i]):
        vmax[s+j+1]=v[i]
    s+=t[i]
vmax[-1]=0
q[0].append(T)
vans=[-1]*(T+1)
for s in q[0]:
    vans[s]=0
for i in range(101):
    while(len(q[i])>0):
        s=q[i].popleft()
        if vans[s]==-1:
            vans[s]=i
        if s>0 and vans[s-1]==-1:
            if vmax[s-1]>i:
                q[i+1].append(s-1)
                vans[s-1]=i+1
            else:
                q[i].append(s-1)
                vans[s-1]=i
        if s<T and vans[s+1]==-1:
            if vmax[s+1]>i:
                q[i+1].append(s+1)
                vans[s+1]=i+1
            else:
                q[i].append(s+1)
                vans[s+1]=i
ans=0
for i in range(T):
    if vans[i+1]==vans[i]+1:
        ans+=vans[i]+0.5
    elif vans[i+1]==vans[i]-1:
        ans+=vans[i+1]+0.5
    elif vmax[i+1]>vans[i+1] or vmax[i]>vans[i]:
        ans+=vans[i]+0.25
    else:
        ans+=vans[i]
print(ans)

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=[0]*(T+1)
from collections import deque
q=[deque() for i in range(101)]
s=0
for i in range(N):
    vmax[s]=min(vmax[s-1],v[i])
    q[vmax[s]].append(s)
    for j in range(t[i]):
        vmax[s+j+1]=v[i]
    s+=t[i]
vmax[-1]=0
q[0].append(T)
vans=[-1]*(T+1)
for s in q[0]:
    vans[s]=0
for i in range(101):
    while(len(q[i])>0):
        s=q[i].popleft()
        if s>0 and vans[s-1]==-1:
            if s-1 not in q[i] and vmax[s-1]>i:
                q[i+1].append(s-1)
                vans[s-1]=i+1
            else:
                q[i].append(s-1)
                vans[s-1]=i
        if s<T and vans[s+1]==-1:
            if s+1 not in q[i] and vmax[s+1]>i:
                q[i+1].append(s+1)
                vans[s+1]=i+1
            else:
                q[i].append(s+1)
                vans[s+1]=i
ans=0
for i in range(T):
    if vans[i+1]==vans[i]+1:
        ans+=vans[i]+0.5
    elif vans[i+1]==vans[i]-1:
        ans+=vans[i+1]+0.5
    elif vmax[i+1]>vans[i+1] or vmax[i]>vans[i]:
        ans+=vans[i]+0.25
    else:
        ans+=vans[i]
print(ans)

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=[0]*(T+1)
from collections import deque
q=[deque() for i in range(101)]
s=0
for i in range(N):
    vmax[s]=min(vmax[s-1],v[i])
    q[vmax[s]].append(s)
    for j in range(t[i]):
        vmax[s+j+1]=v[i]
    s+=t[i]
vmax[-1]=0
q[0].append(T)
vans=[-1]*(T+1)
vans[0]=vans[-1]=0
for i in range(101):
    while(len(q[i])>0):
        s=q[i].popleft()
        if s>0 and vans[s-1]==-1:
            if vmax[s-1]>i:
                q[i+1].append(s-1)
                vans[s-1]=i+1
            else:
                q[i].append(s-1)
                vans[s-1]=i
        if s<T and vans[s+1]==-1:
            if vmax[s+1]>i:
                q[i+1].append(s+1)
                vans[s+1]=i+1
            else:
                q[i].append(s+1)
                vans[s+1]=i
ans=0
for i in range(T):
    if vans[i+1]==vans[i]+1:
        ans+=vans[i]+0.5
    elif vans[i+1]==vans[i]-1:
        ans+=vans[i+1]+0.5
    elif vmax[i+1]>vans[i+1] or vmax[i]>vans[i]:
        ans+=vans[i]+0.25
    else:
        ans+=vans[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
v.append(0)
dp = [0]*(sum(t)+1)
ind = 1
time = sum(t)
for i in range(n):
    for j in range(t[i]):
        if time<=dp[ind-1] or dp[ind-1]-v[i+1]>=t[i]-j:
            dp[ind] = dp[ind-1]-1
            ind += 1
            time -= 1
        else:
            dp[ind] = min(dp[ind-1]+1,v[i])
            ind += 1
            time -= 1
print(float(sum(dp)))

Submission status: Wrong Answer

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)
vt = [min(i,(T-i)) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]
    for j in range(T+1):
        vt[j] = min(vt[j],v[i]+max(0,-(j-ts),(j-te)))
    ts = te
print(max(sum(vt),T**2/4))

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

        totalt = 0
        idx = 0
        for k in range(n):
            totalt += t[k]
            if totalt >= i:
                idx = k
                break
        if vs[i]==vs[i+1] and vs[i]<v[idx]:
            ans += 0.25


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


solve()