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: Runtime Error

Solution code:
def get_distance_and_next_speed(current_speed, max_speed, time, next_max_speed):
	#CASE 1: /---- or -----(CAN REACH THE MAX SPEED) AND THE NEXT MAX SPEED IS EQUAL TO OR BIGGER THAN CURRENT MAX SPEED
	if max_speed <= next_max_speed and max_speed >= current_speed and max_speed - current_speed <= time:
		#max_speed - current_speed = THE DELTA VELOCITY = THE DELTA TIME < t --> CAN REACH THE MAX SPEED
		acceleration_duration = max_speed - current_speed
		max_speed_duration = time - acceleration_duration
		distance = ((max_speed + current_speed) * acceleration_duration) / 2.0 + max_speed_duration * max_speed
		new_current_speed = max_speed
		return distance, new_current_speed
	
	#CASE 2: /(CAN NOT REACH THE MAX SPEED) AND THE NEXT MAX SPEED IS EQUAL TO OR BIGGER THAN CURRENT MAX SPEED
	elif max_speed <= next_max_speed and max_speed > current_speed and max_speed - current_speed > time:
		#CAN NOT REACH THE MAX SPEED IN THIS DURATION
		max_valid_speed = current_speed + t
		distance = (max_valid_speed + current_speed) * t / 2.0
		new_current_speed = max_valid_speed
		return distance, new_current_speed
	
	#CASE 3: /--\ or --\ THE SUM OF VELOCITY CHANGING DURATION SHALL BE EQUAL TO OR SMALLER THAN TIME
	elif max_speed > next_max_speed and max_speed >= current_speed and (max_speed - current_speed) + (max_speed - next_max_speed) <= time:
		#ACCELERATION PART
		acceleration_duration = max_speed - current_speed
		acceleration_distance = (max_speed + current_speed) * acceleration_duration / 2.0
		
		#MAX SPEED PART				#THE DELTA TIME OF ACCELERATION #THE DELTA TIME OF DECELERATION
		max_speed_duration = time - ((max_speed - current_speed) + (max_speed - next_max_speed))
		max_speed_distance = max_speed_duration * max_speed
		
		#DECELERATION PART
		deceleration_duration = max_speed - next_max_speed
		deceleration_distance = deceleration_duration * (max_speed + next_max_speed) / 2.0
		
		distance = acceleration_distance + max_speed_distance + deceleration_distance
		new_current_speed = next_max_speed
		return distance, new_current_speed
	
	#CASE 4: /\ THAT IS IMPOSSIBLE TO REACH THE MAX VELOCITY
	elif max_speed > next_max_speed and max_speed > current_speed and (max_speed - current_speed) + (max_speed - next_max_speed) > time:
		acceleration_duration = (next_max_speed - current_speed + time) / 2.0
		deceleration_duration = time - acceleration_duration
		max_valid_speed = current_speed + acceleration_duration
		
		#ACCELERATION PART
		acceleration_distance = (max_valid_speed + current_speed) * acceleration_duration / 2.0
		
		#DECELERATION PART
		deceleration_distance = (max_valid_speed + next_max_speed) * deceleration_duration / 2.0
		
		distance = acceleration_distance + deceleration_distance
		new_current_speed = next_max_speed
		return distance, new_current_speed

case_number = input()
time_list = [int(x) for x in raw_input().split()]
velocity_list = [int(x) for x in raw_input().split()]
velocity_list.append(0)	#THE FINAL DECELERATION CAN BE SEEN AS A PART WHOSE MAX VELOCITY IS ZERO
CURRENT_SPEED = 0
TOTAL_DISTANCE = 0
for INDEX in xrange(case_number):
	DELTA_DISTANCE, CURRENT_SPEED = get_distance_and_next_speed(current_speed = CURRENT_SPEED, max_speed = velocity_list[INDEX], time = time_list[INDEX], next_max_speed = velocity_list[INDEX + 1])
	TOTAL_DISTANCE += DELTA_DISTANCE
print TOTAL_DISTANCE

Submission status: Runtime Error

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())
  
  dp = ndp
 
print(dp[0]/8)

Submission status: Runtime Error

Solution code:
n = int(input())

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

time = sum(tt);

border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
	temp += tt[i]
	border[i+1] = temp
	start_v[i] = v[i]
	end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0

# print (border)
while t < time :
	t += 0.5
	
	# tle回避
	if t < border[idx+1] and abs(v0- (vlast-0.5) ) < 0.001:
		v0 = vlast - 0.5
		ans += 0.5 * (vlast + v0) / 2
		vlast = v0
		continue

 	vlast = v0

	#直接制約
	v0 = v[idx]
	if t == border[idx+1]:
		idx += 1
#		v0 = min(v0, v[idx])

	for j in range(n+1):
		
		if border[j] <= t:
			#前の時刻からの制約
			temp = end_v[j] + (t - border[j])
			if v0 > temp:
				v0 = temp
		if border[j] >= t:
			#後ろの時刻からの制約
			temp = start_v[j] + (border[j] - t)
			if v0 > temp:
				v0 = temp

#	print(v0)

	# ans += 0.5 * (vlast + v0) / 2
	ans += 0.5 * (vlast + v0) / 2
# 	vlast = v0

print (ans)

Submission status: Runtime Error

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

distance = 0

for i in range(1, n+1):
    former_speed = v[i-1]
    current_speed = v[i]
    next_speed = v[i+1]
    if current_speed >= next_speed:
        end = current_speed - next_speed
        if former_speed >= current_speed:
            start = 0
        else:
            start = current_speed - former_speed
        stay = t[i] - (start + end)
    else:
        end = 0
        if former_speed >= current_speed:
            start = 0
        else:
            start = current_speed - former_speed
        stay = t[i] - (start + end)
    if stay >= 0:
        delta = 0.5 * (former_speed + current_speed) * start + current_speed * stay + 0.5 * (next_speed + current_speed) * end
    else:
        if end >= t[i]:
            delta = 0.5 * (former_speed + next_speed) * t[i]
        else:
            diff = next_speed - former_speed
            end = 0.5 * (diff + t[i])
            start = t[i] - end
            current_speed = former_speed + start
            delta *= 0.5 * (former_speed + current_speed) * start + 0.5 * (next_speed + current_speed) * end
    distance += delta

print(distance)

Submission status: Runtime Error

Solution code:

N=int(input())
T=spaceinput()
v=spaceinput()

Tmax=0

for i in range(N):
    Tmax+=(T[i])
#mv=[0]*(Tmax+1)
mv={}

frange=[x for x in range(2*Tmax+1)]

k=0
sT=T[0]
d=0.5

mv[0]=0
for t in [x/2 for x in range(1,2*Tmax)]:

    if sT<t:
        k+=1
        if k<len(T):
            sT+=T[k]
        else:
            break

    mv[t]=min(v[k],mv[t-0.5]+d)

mv[Tmax]=0

k=N-1
sT=Tmax-T[-1]
for t in reversed([x/2 for x in range(1,2*Tmax)]):
    if sT>t:
        k-=1
        sT-=T[k]

    mv[t]=min(v[k],mv[t],mv[t+d]+d)


res=0
k=0
sT=T[0]
for t in [x/2 for x in range(1,2*Tmax)]:
    if sT<t:
        if t==Tmax-1:
            break
        k+=1
        if k<len(T):
            sT+=T[k]
    res+=mv[t]*0.5

print(res)

Submission status: Runtime Error

Solution code:
def solve(t1,v1,t2,v2,vmax):
  if v1 > vmax or v2 > vmax:
    return -inf
  if t2-t1 < abs(v2-v1):
  	return -inf
  vmax_theory = min(v1,v2)+((t2-t1)+abs(v2-v1))/2.0
  area1 = (vmax_theory-min(v1,v2))**2
  area2 = (abs(v1-v2))**2/2.0
  area3 = (t2-t1)*min(v1,v2) 
  if vmax_theory < vmax:
    return area1-area2+area3
  else: 
    area4 = (vmax_theory-vmax)**2
    return area1-area2+area3-area4


N = int(input())
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))
ts = [0] + ts
vs = [0] + vs

from itertools import accumulate
ts = list(accumulate(ts))

inf = 1000000007
dp = [[-inf for x in range(205)] for y in range(len(ts))]

t_idx = 0

t_tot = sum(ts)

for t_idx in range(len(ts)):
  if t_idx==0:
    dp[t_idx][0] = 0.0
  else:
    for v1 in range(vs[t_idx-1]+1):
      for v2 in range(vs[t_idx]+1):
      	if dp[t_idx-1][v1] < 0 or abs(v2-v1) > ts[t_idx]-ts[t_idx-1]:
      		continue
        dp[t_idx][v2] = max(dp[t_idx][v2],
                            dp[t_idx-1][v1] + solve(ts[t_idx-1], v1, ts[t_idx], v2, vs[t_idx])) 


print("{:.12f}".format(dp[len(ts)-1][0]))

Submission status: Runtime Error

Solution code:
def solve(t1,v1,t2,v2,vmax):
  if v1 > vmax or v2 > vmax:
    return -inf
  if t2-t1 < abs(v2-v1):
  	return -inf
  vmax_theory = min(v1,v2)+((t2-t1)+abs(v2-v1))/2.0
  area1 = (vmax_theory-min(v1,v2))**2
  area2 = (abs(v1-v2))**2/2.0
  area3 = (t2-t1)*min(v1,v2) 
  if vmax_theory < vmax:
    return area1-area2+area3
  else: 
    area4 = (vmax_theory-vmax)**2
    return area1-area2+area3-area4


N = int(input())
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))
ts = [0] + ts
vs = [0] + vs

from itertools import accumulate
ts = list(accumulate(ts))

inf = 1000000007
dp = [[-inf for x in range(205)] for y in range(len(ts))]

t_idx = 0

t_tot = sum(ts)

for t_idx in range(len(ts)):
  if t_idx==0:
    dp[t_idx][0] = 0.0
  else:
    for v1 in range(vs[t_idx-1]+1):
      for v2 in range(vs[t_idx]+1):
      	if dp[t_idx-1][v1] < 0:
      		continue
        dp[t_idx][v2] = max(dp[t_idx][v2],
                            dp[t_idx-1][v1] + solve(ts[t_idx-1], v1, ts[t_idx], v2, vs[t_idx])) 


print("{:.12f}".format(dp[len(ts)-1][0]))

Submission status: Runtime Error

Solution code:

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


T.append(0)
V.append(0)
T_sum= []
tmp_sum = 0
for t in T:
    tmp_sum+=t
    T_sum.append(tmp_sum)

n=0
_range =1000000

def check(t,n,v):
    max_a = 1
    for i in range(n+1,N+1):
        max_speed_i = V[i]
        time_i = T_sum[i-1]
        max_a = min(max_a, (max_speed_i-v)/(time_i-t))
    return (max_a)

ans= 0
v= 0
for i in range(_range):
    t = i/_range*T_sum[-1]


    if t>T_sum[n]:
        n+=1
    max_speed = V[n]
    vp = 1 if check(t,n,v)> -1 else -1
    if vp==1 and v>max_speed:
        vp=0
    v_old=v

    v+=vp/_range *T_sum[-1]
    #print(t,V[n],vp, v)
    ans +=(v+v_old)/2* 1/_range*T_sum[-1]

print(ans)

Submission status: Runtime Error

Solution code:

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


T.append(0)
V.append(0)
T_sum= []
tmp_sum = 0
for t in T:
    tmp_sum+=t
    T_sum.append(tmp_sum)

n=0
_range =100000

def check(t,n,v):
    max_a = 1
    for i in range(n+1,N+1):
        max_speed_i = V[i]
        time_i = T_sum[i-1]
        max_a = min(max_a, (max_speed_i-v)/(time_i-t))
    return (max_a)

ans= 0
v= 0
for i in range(_range):
    t = i/_range*T_sum[-1]


    if t>T_sum[n]:
        n+=1
    max_speed = V[n]
    vp = 1 if check(t,n,v)> -1 else -1
    if vp==1 and v>max_speed:
        vp=0
    v_old=v

    v+=vp/_range *T_sum[-1]
    #print(t,V[n],vp, v)
    ans +=(v+v_old)/2* 1/_range*T_sum[-1]

print(ans)