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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))

T = sum(t)

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

def func(l,r,v,x):
    if x<=l:
        return v+(l-x)
    elif l<x<r:
        return v
    else:
        return v+(x-r)

def getv(x):
    # ret = None
    # for e in eq:
    #     v = func(e[0],e[1],e[2],x)
    #     if ret is None:
    #         ret = v
    #     else:
    #         ret = min(ret,v)
    # return ret
    ret = func(0,0,0,x)
    tt = 0
    for i in range(n):
        ret = min(ret, func(tt,tt+t[i],v[i],x))
        tt += t[i]
    ret = min(ret, func(tt,tt,0,x))
    return ret

ret = 0
lastv = None
for i in range(2*T):
    a1 = i*0.5
    a2 = (i+1)*0.5
    if lastv is not None:
        v1 = lastv
    else:
        v1 = getv(a1)
    v2 = getv(a2)
    lastv = v2

    ret += 0.5*0.5*(v1+v2)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))

T = sum(t)

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

def func(l,r,v,x):
    if x<=l:
        return v+(l-x)
    elif l<x<r:
        return v
    else:
        return v+(x-r)

def getv(x):
    ret = None
    for e in eq:
        v = func(e[0],e[1],e[2],x)
        if ret is None:
            ret = v
        else:
            ret = min(ret,v)
    return ret

ret = 0
lastv = None
for i in range(2*T):
    a1 = i*0.5
    a2 = (i+1)*0.5
    if lastv is not None:
        v1 = lastv
    else:
        v1 = getv(a1)
    v2 = getv(a2)
    lastv = v2

    ret += 0.5*0.5*(v1+v2)
print(ret)

Submission status: Time Limit Exceeded

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

ans = 0
prev_spped = 0

for x in range(1, 2 * t[-1] + 1):
	time = x / 2
	speeds = [time, t[-1] - time]
	for i in range(n):
		if time <= t[i]:
			speeds.append(v[i] + t[i] - time)
		elif t[i] < time <= t[i + 1]:
			speeds.append(v[i])
		else:
			speeds.append(v[i] + time - t[i + 1])
	speed = min(speeds)
	ans += (speed + prev_spped) * 0.25
	prev_spped = speed

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate as ac
o=[]
f=lambda l,r,v:lambda x:v if l<=x<=r else v+(l-x) if 0<=x<=l else v+(x-r)

o.extend([f(0,0,0)])
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())
*c,=ac([0]+a)

for (i,(t,v)) in enumerate(zip(a,b)):
  o.extend([f(c[i],c[i+1],v)])
o.extend([f(c[-1],c[-1],0)])
v=lambda s:min(map(lambda x:x(0.5*s),o))

S=0
for i in range(2*c[-1]):
  S+=0.25*(v(i)+v(i+1))
print(S)

Submission status: Time Limit Exceeded

Solution code:
def v_max(x):#x(sec)における最大速度
    res = x
    
    for i in range(n + 1):
        t_l = t2[i]
        t_r = t2[i + 1]
        
        if 0 <= x < t_l:
            vi = v[i] + (t_l - x)
        elif t_l <= x <= t_r:
            vi = v[i]
        else:
            vi = v[i] + (x - t_r)
            
        res = min(res, vi)
        
    return res

n = int(input())
t = list(map(int, input().split()))
t2 = [0]#累積和
for i in range(n):
    t2.append(t2[i] + t[i])#0, t1, t1 + t2, t1 + t2 + t3, ...のように増えていく
finish_t = t2[-1]#終了時刻
t2.append(finish_t)
v = list(map(int, input().split())) + [0]#v1, v2, ..., 0

#print(t)
#print(t2)
#print(v)

now = 0
v_l = 0
ans = 0
while now < finish_t:
    now += 0.5
    v_r =  v_max(now)
    ans += 0.25 * (v_l + v_r)

    v_l = v_r
    
print(ans)

Submission status: Time Limit Exceeded

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

V = [0] + V + [0]

# 0.前処理
# N+2個の条件をつくる
left = [0]
right = [0]

for i in range(N):
    left.append(right[i])
    right.append(left[-1]+T[i])
    
left.append(right[-1])
right.append(right[-1])

INF = float("inf")
vel = [INF]*(2*right[-1]+1)

# 1.各ステップでの許容測度の最大値の最小値を求める
for t in range(2*right[-1]+1):
    for i in range(N+2):
        if (t/2) < left[i]:
            vel[t] = min(vel[t], -(t/2)+(V[i]+left[i]))
        elif left[i] <= (t/2) and (t/2) <= right[i]:
            vel[t] = min(vel[t], V[i])
        elif (t/2) > right[i]:
            vel[t] = min(vel[t], (t/2)+(V[i]-right[i]))
            

# 2.面積を求める
ans = 0
for t in range(2*right[-1]):
    ans += (1/2)*0.5*(vel[t]+vel[t+1])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

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

upper = []

Ts = 0
for i in range(N):
    upper.append((Ts, V[i]))
    Ts += T[i]
    upper.append((Ts, V[i]))

S = sum(T)
upper.append((0, 0))
upper.append((S, 0))

ans = [0]
Ts = 0
for i in range(N):
    dt = 0
    while True:
        dt += 0.5
        t = Ts + dt
        v = V[i]
        for p in upper:
            v = min(v, p[1] + abs(p[0] - t))
        ans.append(v)
        if dt == T[i]:
            break
    Ts += T[i]

print (sum(ans[1:]) + sum(ans[:-1])) / 4

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

# 各区間の制限速度条件のみを満たす最大速度のグラフを求める
accTs = list(accumulate(ts))
sumT = accTs[-1]
vMaxs = [100] * (2 * sumT + 1)
for v, l, r in zip(vs + [0, 0], [0] + accTs[:-1] + [0, sumT], accTs + [0, sumT]):
    vms = []
    for t2 in range(sumT * 2 + 1):
        t = t2 / 2
        if t <= l:
            vms += [v + l - t]
        elif t <= r:
            vms += [v]
        else:
            vms += [v + t - r]

    # 最小値がその時刻における列車の速度になる
    vMaxs = list(map(min, vMaxs, vms))

print(sum(vMaxs) / 2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
# 解説読んだ後
def maxspeed(left,right,t,vmax):
    if t<=left:
        return vmax+(left-t)
    elif left< t < right:
        return vmax
    else:
        return vmax+t-right
funcs=[]
funcs.append((0,0,0))
left=0
for i in range(N):
    funcs.append((left,left+T[i],V[i]))
    left+=T[i]
funcs.append((left,left,0))
dist=0.0
speed=0
for t in np.arange(0.0,left+0.5,0.5):
    speed2=min(maxspeed(pm[0],pm[1],t,pm[2]) for pm in funcs)
    if 0< t:
        dist+=(speed+speed2)*0.5/2
    speed=speed2
print(dist)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = [0]+[int(i) for i in input().split()]+[0]
v = [int(i) for i in input().split()]+[0]
def f(x,v,t1,t2):
	if x<t1: return v+(t1-x)
	elif t1<=x<=t2: return v
	else: return v+(x-t2)
for i in range(1,n+2): t[i]+=t[i-1]
T,ans = 2*t[-1]+1,0
for i in range(T):
	num = i/2
	for j in range(n+1):
		if i/2<t[j]-100: break
		num = min(num,f(i/2,v[j],t[j],t[j+1]))
	ans+=num/2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = [0]+[int(i) for i in input().split()]+[0]
v = [int(i) for i in input().split()]+[0]
def f(x,v,t1,t2):
	if x<t1: return v+(t1-x)
	elif t1<=x<=t2: return v
	else: return v+(x-t2)
for i in range(1,n+2): t[i]+=t[i-1]
T,ans = 2*t[-1]+1,0
for i in range(T):
	num = i/2
	for j in range(n+1): num = min(num,f(i/2,v[j],t[j],t[j+1]))
	ans+=num/2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = [0]+[int(i) for i in input().split()]+[0]
v = [int(i) for i in input().split()]+[0]
def f(x,v,t1,t2):
	if x<t1: return v+(t1-x)
	elif t1<=x<=t2: return v
	else: return v+(x-t2)
a,ans = [],0
for i in range(1,n+2): t[i]+=t[i-1]
for i in range(2*t[-1]+1):
	num = i/2
	for j in range(n+1): num = min(num,f(i/2,v[j],t[j],t[j+1]))
	a.append(num)
for i in range(len(a)-1): ans+=(a[i]+a[i+1])/4
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def speed_limit(cond_i, time):
    if time < t[cond_i-1]:
        return v[cond_i] + (t[cond_i-1] - time)
    elif time < t[cond_i]:
        return v[cond_i]
    else:
        return v[cond_i] + (time - t[cond_i])

N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
t = [0] + t
v = [0] + v
for i in range(1,N+1):
    t[i] = t[i-1]+t[i]
#print(t)
#print(v)
v_possible = [0]*(2*t[N])
for i in range(1,2*t[N]):
    v_possible[i] = min(i*0.5, t[N]-i*0.5)
    for j in range(N+1):
        v_possible[i] = min(v_possible[i], speed_limit(j, i*0.5))


#print(t)
#print(v)
#print(v_possible)
ans = sum(v_possible)*0.5
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def speed_limit(cond_i, time):
    if time < t[cond_i-1]:
        return v[cond_i] + (t[cond_i-1] - time)
    elif time < t[cond_i]:
        return v[cond_i]
    else:
        return v[cond_i] + (time - t[cond_i])

N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
t = [0] + t
v = [0] + v
for i in range(1,N+1):
    t[i] = t[i-1]+t[i]
#print(t)
#print(v)
v_possible = [0]*(2*t[N])
for i in range(1,2*t[N]):
    v_possible[i] = 0.5*i
    for j in range(N+1):
        v_possible[i] = min(v_possible[i], speed_limit(j, i*0.5))


#print(t)
#print(v)
#print(v_possible)
ans = sum(v_possible)*0.5
print(ans)

Submission status: Time Limit Exceeded

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


Z = [0] * (len(T))
K = [[0, 0]]
for i in range(len(T)-1):
    Z[i+1] = Z[i] + T[i+1]
    K.append([Z[i], Z[i+1]])
gokei_T = sum(T)

K.append([gokei_T, gokei_T])

ans = 0
time_table = [0.5*i for i in range(2*gokei_T+1)]

for time in time_table:
    speed = 10**5
    for k, v in zip(K, V):
        if time <= k[0]:
            tmp = v + (k[0]-time)
        elif k[0] <= time <= k[1]:
            tmp = v
        elif k[1] <= time:
            tmp = v + (time - k[1])

        speed = min(speed, tmp)
    ans += 0.5 * speed

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy

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

Z = [0] * (len(T))
for i in range(len(T)-1):
    Z[i+1] = Z[i] + T[i+1]
gokei_T = sum(T)
K = [[0, 0]]
for i in range(N):
    K.append([Z[i], Z[i+1]])
K.append([gokei_T, gokei_T])

ans = 0
for time in numpy.arange(0, gokei_T, 0.5):
    speed = 10**5
    for k, v in zip(K, V):
        if time <= k[0]:
            tmp = v + (k[0]-time)
        elif k[0] <= time <= k[1]:
            tmp = v
        elif k[1] <= time:
            tmp = v + (time - k[1])

        speed = min(speed, tmp)
    ans += 0.5 * speed

print(ans)

Submission status: Time Limit Exceeded

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

Z = [0] * (len(T))
for i in range(len(T)-1):
    Z[i+1] = Z[i] + T[i+1]

K = [[0, 0]]
for i in range(N):
    K.append([Z[i], Z[i+1]])
K.append([sum(T), sum(T)])

ans = 0
time_table = [0.5*i for i in range(2*sum(T)+1)]

for time in time_table:
    speed = 10**5
    for k, v in zip(K, V):
        if time <= k[0]:
            tmp = v + (k[0]-time)
        elif k[0] <= time <= k[1]:
            tmp = v
        elif k[1] <= time:
            tmp = v + (time - k[1])

        speed = min(speed, tmp)
    ans += 0.5 * speed

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T.insert(0, 0)
T.append(sum(T))
V.insert(0, 0)
V.append(0)

Z = [0] * (len(T))
for i in range(len(T)-1):
    Z[i+1] = Z[i] + T[i+1]


def calc_speed(l, r, x, v):
    if x <= l:
        return v + (l-x)
    if l <= x <= r:
        return v
    if r <= x:
        return v + (x-r)


ans = 0
time_table = [0.5*i for i in range(sum(T)+1)]

for time in time_table:
    speed = 10**5
    for i in range(N+1):
        zero_speed = calc_speed(0, 0, time, 0)
        T_speed = calc_speed(sum(T), sum(T), time, 0)
        speed = min(speed, zero_speed, T_speed, calc_speed(Z[i], Z[i+1], time, V[i+1]))
    ans += 0.5 * speed

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def speed(t, v, l, r):
    if t < l:
        return v + l - t
    if l <= t <= r:
        return v
    if r < t:
        return v + t - r


n = int(input())
ts = np.cumsum(np.array([0] + list(map(int, input().split()))))
vs = list(map(int, input().split()))
conditions = [(0, 0, 0)] + [(vs[i], ts[i], ts[i + 1]) for i in range(n)] + [(0, ts[-1], ts[-1])]

speeds = np.zeros((ts[-1] * 2 + 1, len(conditions)))
for t in range(ts[-1] * 2 + 1):
    for i, (v, l, r) in enumerate(conditions):
        speeds[t, i] = speed(t*0.5, v, l, r)

print(speeds.min(axis=1).sum() / 2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def speed(t, v, l, r):
    if t < l:
        return v + l - t
    if l <= t <= r:
        return v
    if r < t:
        return v + t - r

n = int(input())
ts = np.cumsum(np.array([0] + list(map(int, input().split()))))
vs = list(map(int, input().split()))
conditions = [(0, 0, 0)] + [(vs[i], ts[i], ts[i+1]) for i in range(n)] + [(0, ts[-1], ts[-1])]

speeds = []
for t in range(ts[-1]*2+1):
    speeds.append(min([speed(t*0.5, v, l, r) for v, l, r in conditions]))

print(sum(speeds)/2)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

def upperlimit(ts, vs):
    """
        return value f gives speed limit at time t
    """
    xs = [(-100, 0)]
    t = 0
    for s, v in zip(ts, vs):
        xs.append((t, v))
        t += s
    xs.append((t, 0))
    #print(xs)

    """xs has time of start, instead of end"""
    """ achieve, [)"""
    
    def limit(s):
        """ugh! slow"""
        previous = 0
        for t, v in xs:
            if s == t:
                return min(previous, v)
            if s < t:
                return previous
            else:
                previous = v
        return 0
    return limit, t


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

    banned = set()

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

        if (t, v) in banned:
            continue
        limit = f(t/2) * 2
        if limit < v: 
            """over speeding"""
            previous_limit = f((t-1)/2)*2
            if (a == 0 or a == -1 )and previous_limit > limit:
                """rewind"""
                #print(t, v, a, previous_limit, limit)
                for i in range(limit+1, previous_limit+1):
                    p = (t + 1 - i, i)
                    banned.add(p)
                    p = (t + 2 - i, i)
                    banned.add(p)
                #print(banned)
                #UGH! rewind every thing.
                xs = deque()
                xs.append((0,0,0.0, +1))
            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, -1))
        # keep
        xs.appendleft((t+1, v, r+v, 0))
        # acc
        xs.appendleft((t+1, v+1, r+v+0.5, +1))
    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: Time Limit Exceeded

Solution code:

from collections import deque

def upperlimit(ts, vs):
    """
        return value f gives speed limit at time t
    """
    xs = [(-100, 0)]
    t = 0
    for s, v in zip(ts, vs):
        xs.append((t, v))
        t += s
    xs.append((t, 0))
    #print(xs)

    """xs has time of start, instead of end"""
    """ achieve, [)"""
    
    def limit(s):
        """ugh! slow"""
        previous = 0
        for t, v in xs:
            if s == t:
                return min(previous, v)
            if s < t:
                return previous
            else:
                previous = 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: Time Limit Exceeded

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

time = 0
sum_t = sum(t)
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 < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-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: Time Limit Exceeded

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 < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-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(velo_cap)
print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)

Submission status: Time Limit Exceeded

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

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

def f(l, r, v, x):
	maxv = 0
	if 0 <= x and x < l:
		maxv = v + l - x
	elif l <= x and x <= r:
		maxv = v
	else:
		maxv = v + x - r
	return maxv

def vel(x):
	minv = f(0, 0, 0, x)
	minv = min(minv, f(T, T, 0, x))
	for i in range(n):
		r = ls[i] + t[i]
		minv = min(minv, f(ls[i], r, v[i], x))
	return minv

area = 0
velo = [0] * (2 * T + 1)
for i in range(2*T+1):
	velo[i] = vel(0.5*i)
for i in range(2*T):
	area += 0.25 * (velo[i] + velo[i+1])

print(area)

Submission status: Time Limit Exceeded

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

T = sum(t)

def f(l, r, v, x):
	maxv = 0
	if 0 <= x and x < l:
		maxv = v + l - x
	elif l <= x and x <= r:
		maxv = v
	else:
		maxv = v + x - r
	return maxv

def vel(x):
	minv = f(0, 0, 0, x)
	minv = min(minv, f(T, T, 0, x))
	l = 0
	r = 0
	for i in range(n):
		r += t[i]
		minv = min(minv, f(l, r, v[i], x))
		l += t[i]
	return minv

area = 0
a = 0
for i in range(2*T):
	b = vel(0.5*(i+1))
	area += 0.25 * (a+b)
	a = b

print(area)

Submission status: Time Limit Exceeded

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

T = sum(t)

def f(l, r, v, x):
	maxv = 0
	if 0 <= x and x < l:
		maxv = v + l - x
	elif l <= x and x <= r:
		maxv = v
	else:
		maxv = v + x - r
	return maxv

def vel(x):
	minv = f(0, 0, 0, x)
	minv = min(minv, f(T, T, 0, x))
	l = 0
	r = 0
	for i in range(len(t)):
		r += t[i]
		minv = min(minv, f(l, r, v[i], x))
		l += t[i]
	return minv

area = 0
a = 0
for i in range(2*T):
	b = vel(0.5*(i+1))
	area += 0.25 * (a+b)
	a = b

print(area)

Submission status: Time Limit Exceeded

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

T = sum(t)

def f(l, r, v, x):
	maxv = 0
	if 0 <= x and x < l:
		maxv = v + l - x
	elif l <= x and x <= r:
		maxv = v
	else:
		maxv = v + x - r
	return maxv

def vel(x):
	minv = f(0, 0, 0, x)
	minv = min(minv, f(T, T, 0, x))
	l = 0
	r = 0
	for i in range(len(t)):
		r += t[i]
		minv = min(minv, f(l, r, v[i], x))
		l += t[i]
	return minv

area = 0
velo = [0] * (2 * T + 1)
for i in range(2*T+1):
	velo[i] = vel(0.5*i)
for i in range(2*T):
	area += 0.25 * (velo[i] + velo[i+1])

print(area)

Submission status: Time Limit Exceeded

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

T = sum(t)

def f(l, r, v, x):
	maxv = 0
	if 0 <= x and x < l:
		maxv = v + l - x
	elif l <= x and x <= r:
		maxv = v
	else:
		maxv = v + x - r
	return maxv

def vel(x):
	minv = f(0, 0, 0, x)
	minv = min(minv, f(T, T, 0, x))
	l = 0
	r = 0
	for i in range(len(t)):
		r += t[i]
		minv = min(minv, f(l, r, v[i], x))
		l += t[i]
	return minv

area = 0
for i in range(T):
	area += 0.25 * (vel(i) + 2 * vel(i+0.5) + vel(i+1))

print(area)

Submission status: Time Limit Exceeded

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

val = 0
for i in range(sumt*2):
	if gragh[i] != gragh[i+1]:
		val += ((gragh[i]+gragh[i+1]) * 0.25)
	else:
		val += ((gragh[i]) * 0.5)


print(val)

Submission status: Time Limit Exceeded

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 = max(0,vf-t)
    vi_max = min(v_max,vf+t)
    vf2 = vf*vf
    vt = vf+t
    def it():
      for vi,d in enumerate(dp[vi_min:vi_max+1], start=vi_min):
        vp = (vt+vi)/2
        yield d + 2*vp*vp-vf2-vi*vi - 2*max(0,vp-v_max)**2
    ndp[vf] = max(it(), default=-float('inf'))
  
  dp = ndp
 
print(dp[0]/8)

Submission status: Time Limit Exceeded

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 = dict()
  
  def it():
    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
      yield (vf,max(it(),default=-float('inf')))
  
  dp = dict(it())
 
print(dp[0])

Submission status: Time Limit Exceeded

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
    for vi,d in dp.items():
      if abs(vf-vi) > t or vi > v_max:
        continue
      vp = (t+vi+vf)/2
      d += (2*vp*vp-vf*vf-vi*vi)/2
      if vp > v_max:
        d -= (vp-v_max)**2
      ndp[vf] = max(ndp[vf],d)
  
  dp = ndp

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
#! usr/bin/env python3

#D:Atcoder Express

N = int(input())

gragh = [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):
	gragh.append(0.5*i)

a = gragh[:-1]
a.reverse()
gragh.extend(a)

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

val = 0
for i in range(sumt*2):
	if gragh[i] != gragh[i+1]:
		val += ((gragh[i]+gragh[i+1]) * 0.25)
	else:
		val += ((gragh[i]) * 0.5 )

print(val)

Submission status: Time Limit Exceeded

Solution code:
#! usr/bin/env python3

#D:Atcoder Express

N = int(input())

gragh = [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*2+1):
	gragh.append(0.5*i)


a = gragh[:]

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] = float(v[j])
		else:
			tmp = (v[j]+0.5*(i-t[j+1]*2))
			if gragh[i] > tmp:
				gragh[i] = tmp

a.reverse()
for i in range(sumt*2+1):
	if  gragh[i] > a[i] :
		gragh[i] = a[i]


val = 0
for i in range(sumt*2):
	if gragh[i] != gragh[i+1]:
		val += ((gragh[i]+gragh[i+1]) * 0.25)
	else:
		val += ((gragh[i]) * 0.5 )

print(val)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
time=list(map(int,input().split()))
timetable=list(itertools.accumulate([0]+time))
v_max=list(map(int,input().split()))
dt=0.5
v_table=[i*0.5 if i<sum(time) else (sum(time)*2-i)*0.5 for i in range(sum(time)*2)]
for i in range(n):
    t_s,t_e=timetable[i],timetable[i+1]
    for j in range(len(v_table)):
        if j*dt<t_s:
            v=v_max[i]+(t_s-j*dt)
        elif t_s<=j*dt<=t_e:
            v=v_max[i]
        else:
            v=v_max[i]+(j*dt-t_e)
        v_table[j]=min(v_table[j],v)
print(sum(v_table)*0.5)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(raw_input())
T = map(int, raw_input().split(' '))
V = map(int, raw_input().split(' '))

F = []
for i in xrange(N):
    t_s = sum(T[:i])
    t_e = sum(T[:i+1])
    F.append((t_s, t_e, V[i]))

X = []
time_length = sum(T)
step_num = sum(T) * 2
for step in xrange(step_num):
    t = 0.5 * step
    f = [t, time_length-t]
    for t_s, t_e, v in F:
        if t < t_s:
            f.append(v + (t_s - t))
        elif t_s <= t < t_e:
            f.append(v)
        else:
            f.append(v + (t - t_e))
    X.append(min(f))

print sum(X) / 2

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(raw_input())
T = map(int, raw_input().split(' '))
V = map(int, raw_input().split(' '))

V_MAX = []
for i in range(N):
    if i == 0:
        t_s = 0
        t_e = T[i]
    else:
        t_s = sum(T[:i])
        t_e = sum(T[:i+1])

    v = V[i]
    V_MAX.append([])
    for step in range(sum(T) * 2):
        t = step * 0.5
        if t < t_s:
            V_MAX[i].append(v + (t_s - t))
        elif t_s <= t < t_e:
            V_MAX[i].append(v)
        else:
            V_MAX[i].append(v + (t - t_e))

V_MAX.append([i * 0.5 for i in range(sum(T) * 2)])
V_MAX.append([sum(T) - i * 0.5 for i in range(sum(T) * 2)])

X = []
for step in range(sum(T) * 2):
    X.append(min(v[step] for v in V_MAX))

print sum(X) / 2