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: Accepted

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

bound = [0 for _ in range(N+1)]

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


sum=0
for i in range(N):
    if (bound[i]+bound[i+1]+t[i])/2>v[i]:
        sum+=(bound[i]+v[i])*(v[i]-bound[i])/2
        sum+=(bound[i+1]+v[i])*(v[i]-bound[i+1])/2
        sum+=v[i]*(t[i]-2*v[i]+bound[i]+bound[i+1])
    else:
        sum+=(bound[i+1]-bound[i]+t[i])*0.5*(bound[i+1]+3*bound[i]+t[i])*0.5*0.5
        sum+=(t[i]+bound[i]-bound[i+1])*0.5*(bound[i]+3*bound[i+1]+t[i])*0.5*0.5

print(sum)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))
v = [0]*(sum(T)*2+1)
t,Ti = 0,0
for i in range(N):
    Ti += T[i]*2
    v[t] = min(v[t],V[i])
    while t < Ti:
        if v[t] < V[i]:
            v[t+1] = v[t]+0.5
        else:
            v[t+1] = min(v[t],V[i])
        t += 1
sumT = sum(T)*2
v[sumT] = 0
t,Ti = sumT,sumT
for i in range(N):
    Ti -= T[N-i-1]*2
    while t > Ti:
        if v[t-1] > v[t]+0.5:
            v[t-1] = v[t]+0.5
        t -= 1
Ans = 0
for i in range(sumT):
    Ans += (v[i]+v[i+1])*0.5/2

print(Ans)

Submission status: Accepted

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

def solve(N, T, V):
    from itertools import accumulate
    ds = [0] + list(accumulate(T))
    vs = [0] + [min(V[i], V[i + 1]) for i in range(len(V) - 1)] + [0]
    for i in range(len(vs)):
        d = ds[i]
        vs[i] = min([v + abs(d - ds[j]) for j, v in enumerate(vs)])
    def calc(t, v0, v1, maxv):
        t0 = maxv - v0
        t1 = maxv - v1
        if t0 + t1 < t:
            return t * maxv - t0 * t0 / 2 - t1 * t1 / 2
        else:
            t0 = (t + v1 - v0) / 2
            t1 = (t + v0 - v1) / 2
            v = (t + v0 + v1) / 2
            S = v * t - t0 * t0 / 2 - t1 * t1 / 2
            return S
    r = 0
    for i in range(N):
        c = calc(T[i], vs[i], vs[i + 1], V[i])
        r += c
    return r

print(solve(N, T, V))

Submission status: Accepted

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

for i in range(n):
    M += [V[i]]*T[i]*2
   
M = [min(v1, v2) for v1, v2 in zip([0] + M, M + [0])]



for i in range(1,len(M)):
    M[i] = min(M[i],M[i-1]+0.5)
    
for i in range(len(M)-2,0,-1):
    M[i] = min(M[i],M[i+1]+0.5)
    
ans = 0
for i in range(1,len(M)):
    ans += 0.5*(M[i]+M[i-1])*0.5

print(ans)

Submission status: Accepted

Solution code:
"""
prd_xxx 様のコードを参考にさせていただきました。感謝です...！
https://beta.atcoder.jp/contests/abc076/submissions/1724160
"""

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

maxv = [0]
# グラフを整える準備
for v, t in zip(V, T):
    # 転換地点では低い方に合わせる
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t * 2):
        maxv.append(v)

T = len(maxv)
# 前からグラフを整える
for i in range(T - 1):
    maxv[i + 1] = min(maxv[i+1], maxv[i] + 0.5)

maxv[-1] = 0
# 後ろからグラフを整える
for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)

ans = 0
# 台形計算
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)

Submission status: Accepted

Solution code:
def solve(N, T, V):
    from itertools import accumulate
    ds = [0] + list(accumulate(T))
    vs = [0] + [min(V[i], V[i + 1]) for i in range(len(V) - 1)] + [0]
    for i in range(len(vs)):
        d = ds[i]
        vs[i] = min([v + abs(d - ds[j]) for j, v in enumerate(vs)])
    def calc(t, v0, v1, maxv):
        t0 = maxv - v0
        t1 = maxv - v1
        if t0 + t1 < t:
            return t * maxv - t0 * t0 / 2 - t1 * t1 / 2
        else:
            t0 = (t + v1 - v0) / 2
            t1 = (t + v0 - v1) / 2
            v = (t + v0 + v1) / 2
            S = v * t - t0 * t0 / 2 - t1 * t1 / 2
            return S
    r = 0
    for i in range(N):
        c = calc(T[i], vs[i], vs[i + 1], V[i])
        r += c
    return r
    
if __name__ == '__main__':
    N = int(input())
    T = [int(_) for _ in input().split()]
    V = [int(_) for _ in input().split()]
    print(solve(N, T, V))

Submission status: Accepted

Solution code:
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
MAX_T = 200
MAX_V = 100
INF = 1e9
index = 0
tsum = 0
T = sum(t)
dp = [[-INF] * (2*MAX_V+1) for i in range(2*T+1)]
dp[0][0] = 0.0
for i in range(2*T):
    if i+1 > 2 * (tsum + t[index]):
        tsum += t[index]
        index += 1
    for j in range(2*MAX_V+1):
        jj = 0.5 * j
        if jj > v[index]:
            continue
        if jj < v[index]:
            dp[i+1][j+1] = max((dp[i+1][j+1], dp[i][j] + 0.5 * jj + 0.125))
        if jj > 0:
            dp[i+1][j-1] = max((dp[i+1][j-1], dp[i][j] + 0.5 * jj - 0.125))
        dp[i+1][j] = max((dp[i+1][j], dp[i][j] + 0.5 * jj))

print(dp[2*T][0])

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)


def solve(N, t, v):
    memo = [0]
    for i in range(len(t)):
        memo += ([v[i]] * (t[i]) * 2)
    memo += [0]

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

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

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

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


def main():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    print("{0:4f}".format(solve(N, t, v)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from_start=[0]
for i in range(N):
  for s in range(2*t[i]):
    from_start += [min(from_start[-1]+1, 2*v[i])]

to_goal=[0]
t.reverse()
v.reverse()
for i in range(N):
  for s in range(2*t[i]):
    to_goal += [min(to_goal[-1]+1, 2*v[i])]
to_goal.reverse()
velo=[]
for s in range(2*sum(t)+1):
  velo+=[min(from_start[s],to_goal[s])]
  

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

Submission status: Accepted

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

T=sum(t)
t_len=len(t)

maxv=[0]
for ind_i,i in enumerate(t):
	for j in range(i*2):
		if j==i*2-1:
			if ind_i==t_len-1:
				maxv.append(0)
			else:	
				maxv.append( min(v[ind_i],v[ind_i+1]) )
		else:
			maxv.append(v[ind_i])


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


for i in reversed(range(1,2*T)):
	maxv[i]=min(maxv[i],maxv[i+1]+0.5)
#print maxv

#for ind,i in enumerate(maxv):
#	print ind,i


cnt=0
for i in maxv:
	cnt+=0.5

print sum(maxv)/2

Submission status: Accepted

Solution code:
N = int(input())
ts = [int(i) for i in input().split()]
vmax = [int(i) for i in input().split()]
s = []

v = 0
for i in range(N):
    v = min(v, vmax[i])
    for t in range(ts[i]):
        if v < vmax[i]:
            s.append(v + 0.5)
            v += 1
        else:
            s.append(v)

ts = ts[::-1]
vmax = vmax[::-1]
s = s[::-1]

v = 0
count = 0
for i in range(N):
    v = min(v, vmax[i])
    for t in range(ts[i]):
        if v < vmax[i]:
            if s[count] == v + 0.5:
                s[count] = v + 0.25
            else:
                s[count] = min(v + 0.5, s[count])
            v += 1
        else:
            s[count] = min(v, s[count])
        count += 1

print(sum(s))

Submission status: Accepted

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: Accepted

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, 1
	
	#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 + time
		distance = (max_valid_speed + current_speed) * time / 2.0
		new_current_speed = max_valid_speed
		return distance, new_current_speed, 2
	
	#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, 3
	
	#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:
		#CASE 1 ONLY / WITH NO DECELERATION
		if current_speed + time <= next_max_speed:
			distance = (current_speed + current_speed + time) * time / 2.0
			new_current_speed = current_speed + time
			return distance, new_current_speed, 4
		
		#CASE 2 /\
		else:
			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, 4

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
#PREPROCESS TO SIMPLIFY CASES
velocity_list = velocity_list[::-1]
time_list = time_list[::-1]

for vi in xrange(len(velocity_list) - 1):
	cur_v = velocity_list[vi]
	next_v = velocity_list[vi + 1]
	duration_time = time_list[vi]
	next_v = min(next_v, cur_v + duration_time)
	velocity_list[vi + 1] = next_v

velocity_list = velocity_list[::-1]
time_list = time_list[::-1]

CURRENT_SPEED = 0
TOTAL_DISTANCE = 0
DISTANCE_LIST = [0]
SPEED_LIST = [0]

for INDEX in xrange(case_number):
	#print CURRENT_SPEED, velocity_list[INDEX], time_list[INDEX], velocity_list[INDEX + 1]
	DELTA_DISTANCE, CURRENT_SPEED, STATUS = 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])
	DISTANCE_LIST.append(DELTA_DISTANCE)
	TOTAL_DISTANCE += DELTA_DISTANCE
	SPEED_LIST.append(CURRENT_SPEED)

print '%.10f' % TOTAL_DISTANCE

Submission status: Accepted

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-t22) - (t3**2 - t22**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: Accepted

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)
    while vi >= 0 and dp[vi] is None:
      vi -= 1

    if vi < max(0,vf-t):
      ndp[vf] = None
    else:
      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: Accepted

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




print(dist)

Submission status: Accepted

Solution code:
N = int(input())
T = [int(x) for x in input().split(' ')]
V = [int(x) for x in input().split(' ')]
V.append(0)
s = sum(T)
time = [s]
for i in range(N):
    s -= T[N - 1 - i]
    time.append(s)
time.reverse()

s = 0
answer = 0.0
for i in range(N):
    t = T[i]
    limit = V[i]
    g = V[i + 1]
    for j in range(i + 2, N + 1):
        if V[j] + time[j] - time[i + 1] < g:
            g = V[j] + time[j] - time[i + 1]
    x = (s + g + t) / 2.0
    if t <= limit - s and g >= limit:
        answer += 0.5 * t * (2.0 * s + t)
        s += t
    elif g >= limit:
        answer += 0.5 * (limit ** 2 - s ** 2) + limit * (t - limit + s)
        s = limit
    elif t <= g - s:
        answer += 0.5 * t * (2.0 * s + t)
        s += t
    elif x >= limit and s - g < t:
        answer += limit ** 2 - 0.5 * (s ** 2 + g ** 2) + limit * (t - 2.0 * limit + s + g)
        s = g
    elif s - g < t:
        answer += x ** 2 - 0.5 * (s ** 2 + g ** 2)
        s = g
    elif s - g == t:
        answer += 0.5 * (s + g) * t
        s = g
    else:
        print("error")
        break

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# coding: utf-8

# AtCoder Beginner Contest 076
# D - AtCoder Express

from sys import stdin

# 移動距離を返す
def solve(ts, vs):
  if len(ts) == 0: return 0.0

  time  = sum(ts)  # 総時間
  limit = min(vs)  # 制限速度の下限
  if time / 2.0 <= limit:     # limitまで加速する時間がない
    return (time / 2.0) ** 2  # 半分の時間で加速，残りで減速

  # 制限速度まで達した区間がある
  if limit == 0:
    # その区間を除いて計算
    vzero = [i for i in range(len(vs)) if vs[i] == 0][0]
    return solve(ts[:vzero],     vs[:vzero]) + \
           solve(ts[vzero + 1:], vs[vzero + 1:])

  # 最初に1加速, 最後に1減速
  ts[0]  -= 1
  ts[-1] -= 1
  # 長さ0の区間を削除
  if ts[-1] == 0:
    ts = ts[:-1]
    vs = vs[:-1]
  if ts[0] == 0:
    ts = ts[1:]
    vs = vs[1:]
  # 制限時間を1減らす (= 現在速度を1増やす)
  vs = [v - 1 for v in vs]
  # 1加速, 速度1でtime-2秒移動, 1減速, の移動距離
  dist = time - 2 + 1
  return dist + solve(ts, vs)

# 文字列をintのリストに分解する
def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N = int(stdin.readline())
ts = splitToInt(stdin.readline())
vs = splitToInt(stdin.readline())
if len(ts) != N or len(vs) != N: raise
print(solve(ts, vs))

Submission status: Accepted

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

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

v = list(map(int,input().split()))
v.append(0)
det = [v[i]+t[i-1] for i in range(1,n+1)]

runlen = 0.0
vnow = 0.0
idx = 0
for se in range(2*runt):
    now = se/2
    if t[idx] == now:
        idx += 1
    lim = min(det[idx:])
    if - lim + now + vnow == 0.0:
        vnow -= 0.5
        runlen += vnow*0.5 + 0.25
    elif v[idx] == vnow:
        runlen += vnow*0.5
    else:
        vnow += 0.5
        runlen += vnow*0.5 - 0.25
print(runlen)

Submission status: Accepted

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

maxv = [0]
for v,t in zip(vs,ts):
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t*2):
        maxv.append(v)
T = len(maxv)

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

maxv[-1] = 0
for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i+1] + 0.5)

ans = 0.0
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# coding: utf-8

# AtCoder Beginner Contest 076
# D - AtCoder Express

from sys import stdin

# 移動距離を返す
def solve(ts, vs):
  if len(ts) == 0: return 0.0

  time  = sum(ts)  # 総時間
  limit = min(vs)  # 制限速度の下限
  if time / 2.0 <= limit:     # limitまで加速する時間がない
    return (time / 2.0) ** 2  # 半分の時間で加速，残りで減速

  # 制限速度まで達した区間がある
  if limit == 0:
    # その区間を除いて計算
    vzero = [i for i in range(len(vs)) if vs[i] == 0][0]
    return solve(ts[:vzero],     vs[:vzero]) + \
           solve(ts[vzero + 1:], vs[vzero + 1:])

  # 最初に1加速, 最後に1減速
  n = len(ts)
  ts[0]     -= 1
  ts[n - 1] -= 1
  # 長さ0の区間を削除
  if ts[n - 1] == 0:
    ts = ts[:n - 1]
    vs = vs[:n - 1]
  if ts[0] == 0:
    ts = ts[1:]
    vs = vs[1:]
  # 制限時間を1減らす (= 現在速度を1増やす)
  vs = [v - 1 for v in vs]
  # 1加速, 速度1でtime-2秒移動, 1減速, の移動距離
  dist = time - 2 + 1
  return dist + solve(ts, vs)

# 文字列をintのリストに分解する
def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N = int(stdin.readline())
ts = splitToInt(stdin.readline())
vs = splitToInt(stdin.readline())
if len(ts) != N or len(vs) != N: raise
print(solve(ts, vs))

Submission status: Accepted

Solution code:
n = int(input())

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

time = sum(tt);
INF = 999999
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
new_interval = False
limitation_front =0 # 最初の計算に必要

# print (border)
while t < time :
	t += 0.5
	new_interval = False

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

	if(not new_interval):
		limitation_front += 0.5
		if v0 > limitation_front:
			v0 = limitation_front
	
	if new_interval: 
		limitation_front = INF
		for j in range(n+1):
			if border[j] <= t:
				#前の時刻からの制約
				temp = end_v[j] + (t - border[j])
				if v0 > temp:
					v0 = temp
				if limitation_front > temp:
					limitation_front = temp
			else:
				break
			#print (limitation_front)


	for j in range(n+1):
		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 += (vlast + v0)
	vlast = v0

ans /= 4.0
print (ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from itertools import chain

N = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))

vm = list(chain.from_iterable([v] * (2 * t) for t, v in zip(ts, vs)))
vm = [min(v1, v2) for v1, v2 in zip([0] + vm, vm + [0])]
T = len(vm)

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

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

print(sum((v1 + v2) / 4 for v1, v2 in zip(vm, vm[1:])))

Submission status: Accepted

Solution code:
def D_AtCoder_Express(N, T, V):
    """
    N:時間の区間の総数
    T:各時間区間の秒数
    V:各時間区間において許される最大速度
    """
    from itertools import chain

    # 単位時間を0.5秒としたときの、各時間区間での速度を格納する
    # 0.5秒とする理由は解説参照
    speed = list(chain.from_iterable([v] * (2 * t) for t, v in zip(T, V)))

    # 出発時の速度を0、到着時の速度を0と付け加える
    speed = [min(v1, v2) for v1, v2 in zip([0] + speed, speed + [0])]
    length = len(speed)

    # 制限速度に達しているならその速度を格納し、
    # 達していないなら加速させた速度を格納(加速度は1m/(s・s)と定める)
    speed_previous = 0  # 更新前の速度
    for current in range(1, length):
        speed[current] = speed_previous = min(
            speed[current], speed_previous + 0.5)

    # 同じ処理をリストの逆向きに行う(減速を表す)
    speed_previous = 0
    for current in range(length - 1, 0, -1):
        speed[current] = speed_previous = min(
            speed[current], speed_previous + 0.5)

    # 距離(v-tグラフの面積)は台形法で求める
    # (グラフの形より、これ以上の精度の方法は不要)
    return sum((v1 + v2) * 0.5 / 2 for v1, v2 in zip(speed, speed[1:]))

N = int(input())
T = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]
print(D_AtCoder_Express(N, T, V))

Submission status: Accepted

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

    CT = [0 for x in range(N+1)]  # cumulative time
    M = [float('inf') for x in range(len(T))]

    count = 0
    ct = 0
    for t, v in zip(T, V[:N]):
        CT[count] = ct
        ct += t
        count += 1
    CT[N] = ct

    for n in range(N):
        for i in range(n+1):
            M[i] = min(M[i], V[n+1] + (CT[n+1] - CT[i]))


    now = 0
    S = 0
    for q in range(len(T)):
        future = M[q]
        restriction = V[q]
        for s in range(T[q]*2):
            future -= 0.5
            pnow = now
            now = min(min(future, restriction), now + 0.5)
            S += (now + pnow)/4

    print(S)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#標準入力
n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]

#n個の区間について
dt=[0 for i in range(n)] #区間の時間
v0=[0 for i in range(n)] #各区間の最初の速度
ve=[0 for i in range(n)] #各区間の最後の速度
S=[0 for i in range(n)] #各区間に走った距離（v-tグラフの面積）
ok=0 #ok牧場　後でフラグに使う

#dt, v0, veを格納(v0, veは後で題意を満たすように調整する）----------

for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        dt[i]=t[i]
        ve[i]=min(v[i+1],v[i],v0[i]+dt[i])

#α=(ve-v0)/dtが±1以下になるように調整-----------------------------------------

while ok==0:
    for i in range(n-1):
        if  abs((ve[i+1]-v0[i+1])/dt[i+1]) >1:
                ve[i]=ve[i]-1
                v0[i+1]=v0[i+1]-1

                break
    else:
        ok=1
#------------------------------------------------------------------------------------------------

#各区間に関して、走った距離（v-tグラフの面積）を計算---------------------
for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 

    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)

#------------------------------------------------------------------------------------------------
print(sum(S)) #各区間の走った距離の総和（答え）を出力

Submission status: Accepted

Solution code:
n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(n)]
S1=[0 for i in range(n)]
S2=[0 for i in range(n)]
vel=[0 for i in range(n)]

dt=[0 for i in range(n)]
v0=[0 for i in range(n)]
ve=[0 for i in range(n)]
ok=0



for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        dt[i]=t[i]
        ve[i]=min(v[i+1],v[i],v0[i]+dt[i])

#print(dt)
#print(v0)
#print(ve)

while ok==0:
    for i in range(n-1):
#        if  abs((ve[i]-ve[i+1])/dt[i+1]) >1:
        if  abs((ve[i+1]-v0[i+1])/dt[i+1]) >1:
                ve[i]=ve[i]-1
                v0[i+1]=v0[i+1]-1
#                v0[i]=v0[i]-1
#                print("dt",dt)
#                print("v0",v0)
#                print("ve",ve)
                break
    else:
        ok=1


#print(dt)
#print(v0)
#print(ve)


for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=(ttt-v[i]+v0[i])*(vvv-v[i]) 
    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=0

print(sum(S))

Submission status: Accepted

Solution code:
n = input()
t = map(int, raw_input().split())
v = map(int, raw_input().split())
t = [2 * i for i in t]
v = [2 * i for i in v]
f = [1000 for i in range(sum(t) + 1)]

s = 0
for i in range(n):
	for j in range(s, s + t[i] + 1):
		f[j] = min(f[j], v[i])
	s += t[i]
f[0] = 0
f[s] = 0

for i in range(1, s + 1):
	f[i] = min(f[i], f[i - 1] + 1)

for i in range(s)[::-1]:
	f[i] = min(f[i], f[i + 1] + 1)

print (sum(f[:-1]) + sum(f[1:])) / 8.0