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 numpy

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

max_time = sum(T)
time_limit = T.pop()
speed_limit = V.pop()
time_next = T.pop()
speed_next = V.pop()

ans = 0
speed = 0
cul_time = 0
all_remain_time = max_time
for time in numpy.arange(0, max_time+0.5, 0.5):
    all_remain_time -= 0.5
    remain_time = time_limit - time + cul_time
    ans += speed * 0.5

    if remain_time == 0:
        cul_time += time_limit
        time_limit = time_next
        speed_limit = speed_next
        if T:
            time_next = T.pop()
            speed_next = V.pop()

    if speed_next < speed_limit:
        if remain_time <= speed - speed_next:
            if (remain_time == 0) & (speed <= speed_limit) & (all_remain_time >= speed):
                speed += 1
            speed = max(speed-0.5, 0)
        elif speed + 0.5 <= speed_limit:
            speed += 0.5
    else:
        if (speed + 0.5 <= speed_limit) & (all_remain_time >= speed):
            speed += 0.5



print(ans)

Submission status: Wrong Answer

Solution code:
import numpy

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

max_time = sum(T)
time_limit = T.pop()
speed_limit = V.pop()
time_next = T.pop()
speed_next = V.pop()

ans = 0
speed = 0
cul_time = 0
all_remain_time = max_time
for time in numpy.arange(0, max_time+0.5, 0.5):
    all_remain_time -= 0.5
    remain_time = time_limit - time + cul_time
    ans += speed * 0.5

    if remain_time == 0:
        cul_time += time_limit
        time_limit = time_next
        speed_limit = speed_next
        if T:
            time_next = T.pop()
            speed_next = V.pop()

    if speed_next < speed_limit:
        if remain_time <= speed - speed_next:
            if (remain_time == 0) & (speed <= speed_limit) & (all_remain_time >= speed):
                speed += 1
            speed = max(speed-0.5, 0)
        elif speed + 0.5 <= speed_limit:
            speed += 0.5
    else:
        if (speed + 0.5 <= speed_limit) & (all_remain_time >= speed + 0.5):
            speed += 0.5



print(ans)

Submission status: Wrong Answer

Solution code:
import numpy

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

max_time = sum(T)
time_limit = T.pop()
speed_limit = V.pop()
time_next = T.pop()
speed_next = V.pop()

ans = 0
speed = 0
cul_time = 0
all_remain_time = max_time
for time in numpy.arange(0, max_time+0.5, 0.5):
    all_remain_time -= 0.5
    remain_time = time_limit - time + cul_time
    ans += speed * 0.5

    if remain_time == 0:
        cul_time += time_limit
        time_limit = time_next
        speed_limit = speed_next
        if T:
            time_next = T.pop()
            speed_next = V.pop()

    if speed_next < speed_limit:
        if remain_time <= speed - speed_next:
            if (remain_time == 0) & (speed <= speed_limit) & (all_remain_time >= speed):
                speed += 1
            speed = max(speed-0.5, 0)
        elif speed + 0.5 <= speed_limit:
            speed += 0.5
    else:
        if speed + 0.5 <= speed_limit:
            speed += 0.5

print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque

def upperlimit(ts, vs):
    """
        return value f gives speed limit at time t
    """
    t = 0
    xs = [(t, 0)]
    for s, v in zip(ts, vs):
        t += s
        xs.append((t, v))
    t_last = t
    #print(xs)
    """ts has time of start, instead of end"""
    def limit(s):
        """ugh! slow"""
        for t, v in xs:
            if t_last == s:
                return 0
            if t >= s:
                return v
        return 0
    return limit, t


def foo(ts, vs):
    f, end = upperlimit(ts, vs)
    xs = deque()
    xs.append((0,0,0.0))

    visited = set()

    while True:
        t, v, r = xs.popleft()

        if (t, v) in visited:
            continue
        visited.add((t,v))
        if f(t/2)*2 < v: 
            """over speeding"""
            continue

        #print("%d, %d, %f"%(t, v, r))
        if t >= end * 2:
            """time up"""
            return r/4

        # deacc
        xs.appendleft((t+1, v-1, r+v-0.5))
        # keep
        xs.appendleft((t+1, v, r+v))
        # acc
        xs.appendleft((t+1, v+1, r+v+0.5))
    return 0




if __name__ =="__main__":
    n = int(input())
    ts = tuple(map(int, input().split()))
    vs = tuple(map(int, input().split()))

    print(foo(ts, vs))

Submission status: Wrong Answer

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

time = 0
velo_cap =[float("inf")]*(2*sum(t)+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum(t)+1):
    if s < 2*start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(2*start_t-s))
    elif s<2*goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-2*goal_t))
  time += 2*t[i]
for s in range(2*sum(t)+1):
  velo_cap[s] = min(velo_cap[s],2*sum(t)-s,s)

print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)

Submission status: Wrong Answer

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

def calc_area(start_speed, duration, max_speed, end_speed):

	a1=[0]*(duration*2)
	a2=[0]*(duration*2)

	for i in range(len(a1)):
		if i==0:
			a1[i]=start_speed
		else:
			a1[i]=min(a1[i-1]+0.5,max_speed)

	for i in reversed( range(len(a2)) ):
		if i==len(a2)-1:
			a2[i]=min(end_speed+0.5,max_speed)
		else:
			a2[i]=min(a2[i+1]+0.5,max_speed)

	b=[]
	for i,j in zip(a1,a2):
		b.append( min(i,j) )
	return b
		

calc_area(0, 2, 1, 0)

c=[]
for i in range(N):
	if i==0:
		if N==1:
			c.append( ( 0,t[0],v[0],0 ) )
		else:
			c.append( ( 0,t[0],v[0],min(v[0],v[1]) ) )
	elif i==N-1:
		c.append( ( (min(v[i],v[i-1])),t[i],v[i],0 ) )		
	else:	
		c.append( ( min(v[i],v[i-1]),t[i],v[i],min(v[i],v[i+1]) ) )
#print c

d=[]
for i,j,k,l in c:
	d+=calc_area(i, j, k, l)


print sum(d)/2

Submission status: Wrong Answer

Solution code:
N=input()
t=map(int,raw_input().split())
v=map(int,raw_input().split())
#print N,t,v

def calc_area(start, duration, max_speed, end):

	a1=[0]*(duration*2)
	a2=[0]*(duration*2)

	for i in range(len(a1)):
		if i==0:
			a1[i]=start
		else:
			a1[i]=min(a1[i-1]+0.5,max_speed)
	for i in reversed( range(len(a2)) ):
		if i==len(a2)-1:
			a2[i]=min(end+0.5,max_speed)
		else:
			a2[i]=min(a2[i+1]+0.5,max_speed)

	b=[]
	for i,j in zip(a1,a2):
		b.append( min(i,j) )
	return b


ans=0
for i in range(N):
	if i==0:
		if N==1: 
			ans+=sum(calc_area(0,t[i],v[i],0))/2
		else:
			ans+=sum(calc_area(0,t[i],v[i],v[i+1]))/2
	else:
		if i==N-1:
			ans+=sum(calc_area(min(v[i],v[i-1]),t[i],v[i],0))/2
		else:
			ans+=sum(calc_area( min(v[i],v[i-1]) ,t[i] ,v[i] , min(v[i],v[i+1]) ))/2

print "%.10f"%ans

Submission status: Wrong Answer

Solution code:
N=input()
t=map(int,raw_input().split())
v=map(int,raw_input().split())
#print N,t,v

def calc_area(start, duration, max_speed, end):

	a1=[0]*(duration*2)
	a2=[0]*(duration*2)

	for i in range(len(a1)):
		if i==0:
			a1[i]=start
		else:
			a1[i]=min(a1[i-1]+0.5,max_speed)
	for i in reversed( range(len(a2)) ):
		if i==len(a2)-1:
			a2[i]=min(end+0.5,max_speed)
		else:
			a2[i]=min(a2[i+1]+0.5,max_speed)

	b=[]
	for i,j in zip(a1,a2):
		b.append( min(i,j) )
	return b


ans=0
for i in range(N):
	if i==0:
		if N==1: 
			ans+=sum(calc_area(0,t[i],v[i],0))/2
		else:
			ans+=sum(calc_area(0,t[i],v[i],v[i+1]))/2
	else:
		if i==N-1:
			ans+=sum(calc_area(min(v[i],v[i-1]),t[i],v[i],0))/2
		else:
			ans+=sum(calc_area( min(v[i],v[i-1]) ,t[i] ,v[i] , min(v[i],v[i+1]) ))/2

print ans

Submission status: Wrong Answer

Solution code:
N=input()
t=map(int,raw_input().split())
v=map(int,raw_input().split())
#print N,t,v

def calc_area(start, duration, max_speed, end):

	a1=[0]*(duration*2)
	a2=[0]*(duration*2)

	for i in range(len(a1)):
		if i==0:
			a1[i]=start
		else:
			a1[i]=min(a1[i-1]+0.5,max_speed)
	for i in reversed( range(len(a2)) ):
		if i==len(a2)-1:
			a2[i]=min(end+0.5,max_speed)
		else:
			a2[i]=min(a2[i+1]+0.5,max_speed)

	b=[]
	for i,j in zip(a1,a2):
		b.append( min(i,j) )
	#print b
	return b


c=[]
for i in range(N):
	if i==0:
		if N==1: 
			c+=calc_area(0,t[i],v[i],0)
		else:
			c+=calc_area(0,t[i],v[i],v[i+1])
	else:
		if i==N-1:
			c+=calc_area(min(v[i],v[i-1]),t[i],v[i],0)
		else:
			c+=calc_area(min(v[i],v[i-1]),t[i],v[i],v[i+1])

print sum(c)/2

Submission status: Wrong Answer

Solution code:
N=input()
t=map(int,raw_input().split())
v=map(int,raw_input().split())
#print N,t,v

def calc_area(start, duration, max_speed, end):

	a1=[0]*(duration*2)
	a2=[0]*(duration*2)

	for i in range(len(a1)):
		if i==0:
			a1[i]=start
		else:
			a1[i]=min(a1[i-1]+0.5,max_speed)
	for i in reversed( range(len(a2)) ):
		if i==len(a2)-1:
			a2[i]=min(end+0.5,max_speed)
		else:
			a2[i]=min(a2[i+1]+0.5,max_speed)

	b=[]
	for i,j in zip(a1,a2):
		b.append( min(i,j) )
	return b


ans=0
for i in range(N):
	if i==0:
		if N==1: 
			ans+=sum(calc_area(0,t[i],v[i],0))/2
		else:
			ans+=sum(calc_area(0,t[i],v[i],v[i+1]))/2
	else:
		if i==N-1:
			ans+=sum(calc_area(min(v[i],v[i-1]),t[i],v[i],0))/2
		else:
			ans+=sum(calc_area(min(v[i],v[i-1]),t[i],v[i],v[i+1]))/2

print ans

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
times = map(int, raw_input().split())
speeds = map(int, raw_input().split())

#print(times, speeds)

dst = 0
s = 0

for i in range(n):
    #loop over each section of time
    for j in range(times[i]):
        #j is in 100 1 sec intervals
        if (s < speeds[i]):
            s+= 1
            dst += s - 0.5
            #print(s^2, dst,  "accelerating")
        elif (s > speeds[i]):
            s-= 1
            dst += s + 0.5
        else:
            dst += s

dst -= (s*s)/2
print(dst)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

#0, end端点条件: y <= x, y <= -(x - end)
#それ以外:隣り合う
#1秒ずつに対してどこまで上に行けるかを見ればいい
# plotしてみる

xy = []

#y上限
mae = 0
for i in range(n):
    x = np.linspace(mae, mae + t[i], 2*t[i] + 1)
    mae += t[i]
    y = x * 0 + v[i]
    xy.append([x, y])
#start条件
x = np.linspace(0, mae, 2*(mae) + 1)
y = x
xy.append([x, y])
#end条件
x = np.linspace(0, mae, 2*mae + 1)
y = -x + mae
xy.append([x, y])

#隣り合う条件
mae2 = t[0]
for i in range(n - 1):
    if v[i] < v[i+1]:
        x = np.linspace(mae2, mae, 2*(mae - mae2) + 1)
        y = x - mae2 + v[i]
    else:
        x = np.linspace(0, mae2, 2*(mae2) + 1)
        y = -1 * x + mae2 + v[i + 1]
    xy.append([x, y])

ans = 0
now = 0
for i in range(1, 2*mae + 1):
    next = []
    for point in xy:
        if i in (2*point[0]).astype(np.int64):
            next.append(point[1][np.where((2*point[0]).astype(np.int64) == i)[0]])
    m = min(next)
    #台形の面積
    ans += (now + m)/4
    now = m
print(ans[0])

Submission status: Wrong Answer

Solution code:
n = int(input())
            
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))
vs.append(0)

vout_r = []
vout_r.append(0)

for i in range(1,n+1):
    voutcur = min(vs[-i]+ts[-i], vs[-(i+1)])
    vout_r.append(voutcur)
    
v_out = vout_r[::-1]
v_out[0] = 0

for i in range(n-1):
    voutcur = v_out[i] + ts[i]
    v_out[i+1] = min(voutcur,v_out[i+1])


v_out[0] = 0
    
S = 0

for i in range(n):
    tin = vs[i] - v_out[i]
    tout = vs[i] - v_out[i+1]
    
    if tin+tout <= ts[i]:
        S += ts[i]*vs[i] - 0.5*(tin**2+tout**2)
    else:
        lm = abs(v_out[i]-v_out[i+1])
        l = ts[i]+lm
        S += 0.25*(l**2) - 0.5*(lm**2)

print(S)

Submission status: Wrong Answer

Solution code:
n = int(input())
            
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))
vs.append(0)

vout_r = []
vout_r.append(0)

for i in range(1,n+1):
    voutcur = min(vs[-i]+ts[-i], vs[-(i+1)])
    vout_r.append(voutcur)

v_out = vout_r[::-1]
v_out[0] = 0
    
S = 0

for i in range(n):
    tin = vs[i] - v_out[i]
    tout = vs[i] - v_out[i+1]
    
    if tin+tout < ts[i]:
        S += ts[i]*vs[i] - 0.5*(tin**2+tout**2)
    else:
        lm = abs(v_out[i]-v_out[i+1])
        l = ts[i]+lm
        S += 0.25*(l**2) - 0.5*(lm**2)

print(S)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = [float(x) for x in input().rsplit()]
v = [float(x) for x in input().rsplit()]
t_0 = 0
t_now=0
v_0 = 0
v_now = 0
x = 0
t_end = sum(t)
for i in range(N-1):
    if t[i] > v[i] - v_now:
        x += (1 / 2) * (v[i] - v_now) ** 2
        v_now = v[i]
        x += v[i] * (t[i] - (v[i] - v_now))
    else :
        x+=t[i]*t[i]*(1/2)+v_now*t[i]
        v_now+=t[i]
    t_now +=t[i] 
x +=  (1 / 2) *(t_end-t_now) ** 2
print(x)

Submission status: Wrong Answer

Solution code:
#! usr/bin/env python3

#D:Atcoder Express
#TLEシテシマッタ

from collections import deque

N = int(input())

gragh = deque([])
tmp = deque([0])

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

for i in range(1,N):
	t[i] += t[i-1]
t.insert(0,0)

sumt = t[-1]

for i in range(1,sumt+1):
	tmp.append(0.5*i)

gragh.extend(tmp)
tmp.pop()
tmp.reverse()
gragh.extend(tmp)


for j in range(N):
	for i in range(1,sumt*2+1):
		if t[j]*2 > i:
			tmp = (t[j]+v[j]-0.5*i)
			if gragh[i] > tmp:
				gragh[i] = tmp
		elif t[j]*2 <= i <= (t[j+1]*2) :
			if gragh[i] > v[j]:
				gragh[i] = v[j]
		else:
			tmp = (v[j]+0.5*(i-t[j+1]*2))
			if gragh[i] > tmp:
				gragh[i] = tmp


print(gragh)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    Tn = tuple(map(int, input().split()))
    Vn = tuple(map(int, input().split()))

    t = (0,) + Tn + (0,)
    v = (0,) + Vn + (0,)
    maxv = [0]
    for i in range(1, N + 1):
        if v[i-1] < v[i] > v[i+1]:
            maxv += [v[i]] * (t[i] * 2 - 1)
        elif v[i-1] > v[i] < v[i+1]:
            maxv += [v[i]] * (t[i] * 2 + 1)
        else:
            maxv += [v[i]] * t[i] * 2
    maxv += [0]

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

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

    s = 0
    for i in range(cnt - 1):
        s += (maxv[i] + maxv[i+1]) * 0.5 / 2
    print(s)

main()

Submission status: Wrong Answer

Solution code:
num = int(input())
in1 = input().split(" ")
in2 = input().split(" ")
times = [0]
ct = 0
for a in range(num):
    in1[a] = int(in1[a])
    in2[a] = int(in2[a])
for a in range(num):
    ct += in1[a]
    times.append(ct)
vlimit = []
for a in range(1,num):
    vlimit.append(min(in2[a-1],in2[a]))
vlimit.append(in2[num-1])
print(in1,in2)
print(times,vlimit)
 
bairitu = 2
 
last = times[len(times)-1]
limit = [0 for a in range(last*bairitu+1)]
 
for a in range(last*bairitu):
    limit[a] = round(min(a / bairitu, last - a / bairitu),2)
for a in range(len(vlimit)):
    start = times[a] * bairitu
    end = times[a+1] * bairitu
    for b in range(start,end):
        limit[b] = min(limit[b],in2[a])
# print(str(limit))
 
for a in range(len(vlimit)):
    for b in range(0,times[a+1]*bairitu):
        limit[b] = min(limit[b],times[a+1] - b / bairitu + vlimit[a])
    for b in range(times[a+1]*bairitu+1,last*bairitu+1):
        limit[b] = min(limit[b],b / bairitu - times[a+1] + vlimit[a])
 
ans = 0
for a in range(1,len(limit)):
    ans += (limit[a] + limit[a-1])/ bairitu / 2
print(ans)

Submission status: Wrong Answer

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

def f(n, ts, vs):
    sumOfT = sum(ts)

    t = 0
    k = 0
    k1s = [k]

    for i in range(n-1):
        t += ts[i]
        k = min(k, vs[i] - t)
        k1s.append(k)

    t = sumOfT
    k = t
    k2s = [k]

    for i in range(n-1, 0, -1):
        t -= ts[i]
        k = min(k, vs[i] + t)
        k2s.insert(0, k)

    t0 = 0
    d = 0

    for t, v, k1, k2  in zip(ts, vs, k1s, k2s):
        # t0 制限速度がv である開始時刻
        # t1 加速を終わらせる時刻
        # t2 減速を始める時刻
        # t3 制限速度がv である終了時刻

        t3 = t0 + t

        t1 = v - k1
        t2 = k2 - v
        
        if t1 > t2:
            t1 = (k2 - k1)/2
            t2 = t1

        if t0 < t1:
            t12 = min(t1, t3)
            d +=  k1*(t12-t0) + (t12**2 -t0**2)/2

        dt = min(t2, t3) - max(t0, t1)
        if dt > 0:
            d += v*dt

        if t2 < t3:
            t22 = max(t2, t0)
            d +=  k2*(t3-t2) - (t3**2 - t2**2)/2

        t0 = t3
        
    return d


def test():
    assert(f(1, [100], [30]) == 2100)
    assert(f(2, [60,50], [34,38]) == 2632)
    assert(f(3, [12, 14, 2], [6, 2, 7]) == 76)
    assert(f(1, [9], [10]) == 20.25)
    assert(f(10,[64, 55, 27, 35, 76, 119, 7, 18, 49, 100],[29, 19, 31, 39, 27, 48, 41, 87, 55, 70]) == 20291)


def main():
    n = int(input())
    ts = list(map(int, input().split()))
    vs = list(map(int, input().split()))

    print('{0:.4f}'.format(f(n, ts, vs)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def f(n, ts, vs):
    sumOfT = sum(ts)

    t = 0
    k = 0
    k1s = [k]

    for i in range(n-1):
        t += ts[i]
        k = min(k, vs[i] - t)
        k1s.append(k)

    t = sumOfT
    k = t
    k2s = [k]

    for i in range(n-1, 0, -1):
        t -= ts[i]
        k = min(k, vs[i] + t)
        k2s.insert(0, k)

    t0 = 0
    d = 0

    for t, v, k1, k2  in zip(ts, vs, k1s, k2s):
        # t0 制限速度がv である開始時刻
        # t1 加速を終わらせる時刻
        # t2 減速を始める時刻
        # t3 制限速度がv である終了時刻

        t3 = t0 + t

        t1 = v - k1
        t2 = k2 - v
        
        if t1 > t2:
            t1 = (k2 - k1)/2
            t2 = t1

        if t0 < t1:
            d +=  k1*(t1-t0) + (t1**2 -t0**2)/2

        dt = min(t2, t3) - max(t0, t1)
        if dt > 0:
            d += v*dt

        if t2 < t3:
            d +=  k2*(t3-t2) - (t3**2 - t2**2)/2

        t0 = t3
        
    return d


def test():
    assert(f(1, [100], [30]) == 2100)
    assert(f(2, [60,50], [34,38]) == 2632)
    assert(f(3, [12, 14, 2], [6, 2, 7]) == 76)
    assert(f(1, [9], [10]) == 20.25)
    assert(f(10,[64, 55, 27, 35, 76, 119, 7, 18, 49, 100],[29, 19, 31, 39, 27, 48, 41, 87, 55, 70]) == 20291)


def main():
    n = int(input())
    ts = list(map(int, input().split()))
    vs = list(map(int, input().split()))

    print('{0:.4f}'.format(f(n, ts, vs)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):

  ndp = [None]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi = min(len(dp)-1,vf+t)
    vp = (vf+t+vi)/2
    if vi < vf-t:
      ndp[vf] = -float('inf')
    else:
      ndp[vf] = dp[vi] + 2*vp*vp-vf*vf-vi*vi - 2*max(0,vp-v_max)**2
  dp = ndp
 
print(dp[0]/8)

Submission status: Wrong Answer

Solution code:
from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):

  ndp = [None]*(min(vf_max,v_max)+1)

  temp = min(len(dp)-1,v_max)
  
  for vf in range(len(ndp)):
    vi = min(temp,vf+t)
    vp = (vf+t+vi)/2
    ndp[vf] = dp[vi] + 2*vp*vp-vf*vf-vi*vi - 2*max(0,vp-v_max)**2
  dp = ndp
 
print(dp[0]/8)

Submission status: Wrong Answer

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

def calculate_distance(v0,v1,v2,t):
    if v0+t <= v1 and v0+t <= v2:
        return ((v0 + t) * t) - ((t**2) / 2), v0 + t
    elif v0 + t >= v1 and v0 + t <= v2:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    elif v0 + t >= v2 and v2 >= v1:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    else:
        t1 = v1 - v0
        t2 = t - v1 + v2
        if t1 <= t2:
            return (v1 * t) - ((t1 ** 2) / 2) - (((t - t2) ** 2) / 2), v2
        else:
            t3 = (t1 + t2) / 2
            if t3 <= 0:
                return (t * v0) / 2, v2
            else:
                return ((v0 + t3) * t) - ((t3 ** 2) / 2) - (((t - t3) ** 2) / 2), v2

v.append(0)

total = 0
v0 = 0


for i in range(n):
    v1 = v[i]
    if i < n-1:
        v2 = min(v[i+1], v[i+2]+t[i+1])
        dis ,v0 = calculate_distance(v0,v1,v2,t[i])
        total += dis
    else:
        dis, v0 = calculate_distance(v0,v1,0,t[i])
        total += dis

print(total)

Submission status: Wrong Answer

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

def calculate_distance(v0,v1,v2,t):
    if v0+t <= v1 and v0+t <= v2:
        return ((v0 + t) * t) - ((t**2) / 2), v0 + t
    elif v0 + t >= v1 and v0 + t <= v2:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    elif v0 + t >= v2 and v2 >= v1:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    else:
        t1 = v1 - v0
        t2 = t - v1 + v2
        if t1 <= t2:
            return (v1 * t) - ((t1 ** 2) / 2) - (((t - t2) ** 2) / 2), v2
        else:
            t3 = (t1 + t2) / 2
            if t3 <= 0:
                return (t * v0) / 2, v2
            else:
                return ((v0 + t3) * t) - ((t3 ** 2) / 2) - (((t - t3) ** 2) / 2), v2

total = 0
v0 = 0

for i in range(n):
    v1 = v[i]
    if i != n-1:
        v2 = min(v[i+1], t[i+1])
        dis ,v0 = calculate_distance(v0,v1,v2,t[i])
        total += dis
    else:
        dis, v0 = calculate_distance(v0,v1,0,t[i])
        total += dis

print(total)

Submission status: Wrong Answer

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

def calculate_distance(v0,v1,v2,t):
    if v0+t <= v1 and v0+t <= v2:
        return ((v0 + t) * t) - ((t**2) / 2), v0 + t
    elif v0 + t >= v1 and v0 + t <= v2:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    elif v0 + t >= v2 and v2 >= v1:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    else:
        t1 = v1 - v0
        t2 = t - v1 + v2
        if t1 <= t2:
            return (v1 * t) - ((t1 ** 2) / 2) - (((t - t2) ** 2) / 2), v2
        else:
            t3 = (t1 + t2) / 2
            if t3 <= 0:
                return (t * v0) / 2, v2
            else:
                return ((v0 + t3) * t) - ((t3 ** 2) / 2) - (((t - t3) ** 2) / 2), v2

total = 0
v0 = 0

for i in range(n):
    if i != n-1:
        dis ,v0 = calculate_distance(v0,v[i],v[i+1],t[i])
        total += dis
    else:
        dis, v0 = calculate_distance(v0,v[i],0,t[i])
        total += dis

print(total)

Submission status: Wrong Answer

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

def calculate_distance(v0,v1,v2,t):
    if v0+t <= v1 and v0+t <= v2:
        return ((v0 + t) * t) - ((t**2) / 2), v0 + t
    elif v0 + t >= v1 and v0 + t <= v2:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    elif v0 + t >= v2 and v2 >= v1:
        return (v1 * t) - (((v1 - v0) ** 2) / 2), v1
    else:
        t1 = v1 - v0
        t2 = t - v1 + v2
        if t1 <= t2:
            return (v1 * t) - ((t1 ** 2) / 2) - (((t - t2) ** 2) / 2), v2
        elif t2 <= 0:
            return (t * v0) / 2, v2
        else:
            t3 = (t1 - t2) / 2
            return ((v0 + t3) * t) - ((t3 ** 2) / 2) - (((t - t3) ** 2) / 2), v2

total = 0
v0 = 0

for i in range(n):
    if i != n-1:
        dis ,v0 = calculate_distance(v0,v[i],v[i+1],t[i])
        total += dis
    else:
        dis, v0 = calculate_distance(v0,v[i],0,t[i])
        total += dis

print(total)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = list(map(int,input().split()))
T = [0]
tot = 0
for i in range(len(t)):
    tot += t[i]
    T.append(tot)
T = list(map(lambda x: x*2,T))
v = list(map(int,input().split()))
v.append(0)
curv = 0
dist = 0
curt = 0
#print(T)
#print(v)

for i in range(N):
    for _ in range(T[i], T[i+1]):
        prev = curv
        ok = 1
        #if (0 < T[j+1]-curt <= curv - v[j+1] for j in range(N)):
            #print(T[1],curt,curv,v[1])
        for j in range(N-i):
            if T[i+j+1]/2.0 - curt > curv - v[i+j+1]:
                continue
            else:
                ok = 0
                break
        if ok == 1:
            if curv < v[i]:
                curv += 0.5
        elif ok == 0:
            curv -= 0.5
        curt += 0.5
        dist +=(prev+curv) / 4.0

Submission status: Wrong Answer

Solution code:
N = int(input())
t = list(map(int,input().split()))
T = [0]
tot = 0
for i in range(len(t)):
    tot += t[i]
    T.append(tot)
v = list(map(int,input().split()))
v.append(0)
curv = 0
dist = 0
curt = 0
#print(T)
#print(v)

for i in range(N):
    for _ in range(T[i], T[i+1]):
        prev = curv
        ok = 1
        #if (0 < T[j+1]-curt <= curv - v[j+1] for j in range(N)):
            #print(T[1],curt,curv,v[1])
        for j in range(N-i):
            if T[i+j+1] - curt > curv - v[i+j+1]:
                continue
            else:
                ok = 0
                break
        if ok == 1:
            if curv < v[i]:
                curv += 1
        elif ok == 0:
            curv -= 1
        curt += 1
        dist +=(prev+curv) / 2.0




print(dist)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = list(map(int,input().split()))
T = [0]
tot = 0
for i in range(len(t)):
    tot += t[i]
    T.append(tot)
v = list(map(int,input().split()))
v.append(0)
curv = 0
dist = 0
curt = 0
ok = 1
#print(T)
#print(v)

for i in range(N):
    for _ in range(T[i], T[i+1]):
        prev = curv
        ok = 1
        #if (0 < T[j+1]-curt <= curv - v[j+1] for j in range(N)):
            #print(T[1],curt,curv,v[1])
        for j in range(N-i):
            #print(curv, curt, T[i+j+1], v[i+j+1])
            if T[i+j+1] - curt > curv - v[i+j+1]:
                pass
            else:
                ok = 0
                break
        if ok == 1:
            if curv < v[i]:
                curv += 1
        elif ok == 0:
            curv -= 1
        curt += 1
        dist +=(prev+curv) / 2.0




print(dist)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = list(map(int,input().split()))
T = [0]
tot = 0
for i in range(len(t)):
    tot += t[i]
    T.append(tot)
v = list(map(int,input().split()))
v.append(0)
curv = 0
dist = 0
curt = 0
ok = 1
print(T)
print(v)

for i in range(N):
    for _ in range(T[i], T[i+1]):
        prev = curv
        ok = 1
        #if (0 < T[j+1]-curt <= curv - v[j+1] for j in range(N)):
            #print(T[1],curt,curv,v[1])
        for j in range(N-i):
            #print(curv, curt, T[i+j+1], v[i+j+1])
            if T[i+j+1] - curt > curv - v[i+j+1]:
                pass
            else:
                ok = 0
                break
        if ok == 1:
            if curv < v[i]:
                curv += 1
        elif ok == 0:
            curv -= 1
        curt += 1
        dist +=(prev+curv) / 2.0




print(dist)

Submission status: Wrong Answer

Solution code:
from itertools import chain
from collections import defaultdict
 
N = int(input())
T = tuple(map(int,input().split()))
V = tuple(map(int,input().split()))
 
dp = {0:0}
 
for t,v_max in zip(T,V):
 
  ndp = defaultdict(int)
 
  for vf in range(2*v_max+1):
    vf /= 2
    def it():
      for vi,d in dp.items():
        if abs(vf-vi) > t or vi > v_max:
          continue
        vp = (t+vi+vf)/2
        yield d + (2*vp*vp-vf*vf-vi*vi)/2 - max(0,vp-v_max)**2
    
    ndp[vf] = max(it(),default=0)
  
  dp = ndp
 
print(dp[0])

Submission status: Wrong Answer

Solution code:
from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):
  ndp = [0]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi_min = max(0,vf-t)
    vi_max = min(v_max,vf+t)
    def it():
      for vi,d in enumerate(dp[vi_min:vi_max+1], start=vi_min):
        vp = (t+vi+vf)/2
        yield d + 2*vp*vp-vf*vf-vi*vi - 2*(max(0,vp-v_max))**2
    ndp[vf] = max(it(), default=0)
  
  dp = ndp
 
print(dp[0]/8)