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 = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]

T_p = [0,0]
temp = 0
for tt in T:
    temp += tt
    T_p.append(temp)
T_p.append(temp)

Tmax = temp

def vv(i,tt):
    a = T_p[i]
    b = T_p[i + 1]
    if i == 0 or i == N + 1:
        vmax = 0
    else:
        vmax = V[i - 1]
    
    if tt >= b:
        res = tt - b + vmax
    elif tt <= a:
        res = a - tt + vmax
    else:
        res = vmax

    return res

mints = [min([vv(i, tt/2) for i in range(N + 2)]) for tt in range(2 * Tmax + 1)]

res = 0
for i in range(len(mints) -1 ):
    res += (mints[i] + mints[i + 1])/4

print(res)

Submission status: Accepted

Solution code:
N = int( input())
T = list( map( int, input().split())) + [0]
V = list( map( int, input().split())) + [0]
now = 0
end = min( V[0], now + T[0])
ans = 0
for i in range(N):
    # print(i)
    t = T[i]
    v = V[i]
    end = min( v, now + t)
    plus = 0
    for j in range(i, N):
        end = min( end, V[j+1]+plus)
        plus += T[j+1]
    x, y = (end + t - now)/2, (end + t + now)/2
    # print(now, end,v,t,x,y)
    if y <= v:
        # print("T")
        # print((now+y)*x/2, (end+y)*(t-x)/2)
        ans += (now+y)*x/2 + (end+y)*(t-x)/2
        # print((now+y)*x/2 + (end+y)*(t-x)/2)
    else:
        # print("D")
        # print((v+now)*(v-now)/2, (v+end)*(v-end)/2, v*(end-2*v+t+now))
        ans += (v+now)*(v-now)/2 + (v+end)*(v-end)/2+v*(end-2*v+t+now)
        # print((v+now)*(v-now)/2 + (v+end)*(v-end)/2+v*(end-2*v+t+now))
    now = end
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()]

import itertools
tv = [0] + list(itertools.chain(*[[v] * t * 2 for t, v in zip(T, V)])) + [0]
for i in itertools.accumulate(T):
    tv[i * 2] = min(tv[i * 2], tv[i * 2 + 1])
for i in range(len(tv)-1, 0, -1):
    if tv[i] < tv[i-1] - 0.5:
        tv[i-1] = tv[i] + 0.5
    elif tv[i] > tv[i-1] + 0.5:
        for j in range(i, len(tv) - 1):
            if tv[j-1] + 0.5 < tv[j]:
                tv[j] = tv[j-1] + 0.5
            else:
                break
print(sum([(v1 + v2) * 0.5 * 0.5 for v1, v2 in zip(tv[1:], tv[:-1])]))

Submission status: Accepted

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

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

ct = 0
for t,v in zip(T,V):
    for i in range(ct,ct+t+1):
        maxv[i] = min(maxv[i], v)
    ct += t

for i in range(sumt):
    maxv[i+1] = min(maxv[i+1], maxv[i] + 1)
for i in reversed(range(sumt)):
    maxv[i] = min(maxv[i], maxv[i+1] + 1)

print(sum(maxv) / 4)

Submission status: Accepted

Solution code:
v = 0
t = 0
n = int(input())
T = [0] + list(map(int, input().split())) + [0]
V = [0] + list(map(int, input().split())) + [0]
cumT = [0] * (len(T) + 1)
for i in range(len(T)):
    cumT[i + 1] = cumT[i] + T[i]
imos = [1000] * (sum(T) + 1)

for i in range(len(T)):
    for j in range(T[i]):
        imos[cumT[i] + j] = V[i]
horizon = imos.copy()
for i in range(len(T)):
    for j in range(len(imos) - cumT[i + 1]):
        imos[cumT[i + 1] + j] = min([imos[cumT[i + 1] + j], V[i] + j])
    for j in range(cumT[i + 1]):
        imos[cumT[i] - j] = min([imos[cumT[i] - j], V[i] + j])

ret = 0.0
for i in range(len(imos) - 1):
    ret += (imos[i] + imos[i + 1] + 0.5 if imos[i] == imos[i + 1] and imos[i] < horizon[i] else imos[i] + imos[i + 1]) / 2
print(ret)

Submission status: Accepted

Solution code:
N = int(input())
T = [int(i) for i in input().split()]
L = [0]
for i in range(N):
    L.append(L[i] + T[i])
V = [int(i) for i in input().split()]

def VM(x, i): #x秒後に条件iがとり得る速度
    if 0 <= x <= L[i]:
        return V[i] + (L[i] - x)
    elif L[i] < x <= L[i+1]:
        return V[i]
    else:
        return V[i] + (x - L[i+1])

Search = [[] for i in range(N)] #設定された最高速度よりも小さくなり得る条件を探索
for i in range(N):
    for j in range(N):
        if i < j and V[i] - V[j] > L[j] - L[i+1]:
            Search[i].append(j)
        elif i > j and V[i] - V[j] > L[i] - L[j+1]:
            Search[i].append(j)

maxV = [float("inf") for i in range(2*L[-1]+1)]
for i in range(N):
    for j in range(2 * L[i], 2 * L[i+1] + 1):
        maxV[j] = min(V[i], j * 0.5, L[-1] - j * 0.5) #初期化
        for s in Search[i]:
            maxV[j] = min(maxV[j], VM(j * 0.5, s))
Ans = 0
for i in range(2*L[-1]):
    Ans += (maxV[i] + maxV[i+1])/4
print(Ans)

Submission status: Accepted

Solution code:
N=int(input())
t_List=[int(i) for i in input().split()]
t_Table=[0]
for i in range(N):
  t_Table.append(t_Table[i]+t_List[i])
v_List=[int(i) for i in input().split()]
v_List.append(0)
Class=0
t=0
v=0
L=0
check=0
while t<=t_Table[-1]:
  for i in range(Class+1,N+1):
    if t_Table[i]!=t:
      if (v_List[i]-v)/(t_Table[i]-t)==-1:
        L+=v/2-1/8
        v+=-0.5
        check=-1
        break
  if check!=-1: 
    if v==v_List[Class]:
      L+=v/2
    else:
      L+=v/2+1/8
      v+=0.5
  t+=0.5
  if t_Table[Class+1]==t and Class<=N-2:
    Class+=1
    check=0
print(L)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T0 = sum(T)
INF = float("inf")
M = 2 * T0 + 1
l, r = 0, 0
maxv = [INF] * M
for i in range(N):
    l = r
    r += T[i]
    for k in range(2 * l, 2 * r + 1):
        maxv[k] = min(maxv[k], V[i])

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

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


ans = 0
for i in range(1, M):
    ans += 0.25 * (maxv[i] + maxv[i - 1])

print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
t = reads()
v = reads()
psumt = [0] + list(accumulate(t))
T = psumt[-1]

vs = [0] * (T+1)
ans = 0
for ss in range(0, 2 * T):
  s = ss / 2
  m = min(
    abs(s),
    min(v[i] + (abs(psumt[i] - s) + abs(psumt[i+1] - s) - t[i]) / 2 for i in range(N)),
    abs(T-s)
  )
  ans += m / 2
print('%.9f' % ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

def trapezoid(St, En, H, i):
    if St+H[i][0] >= En-H[i][0]:
        return (En-St)**2/4
    result = H[i][0]*(En-St-H[i][0])
    if H[i][1] > St + H[i][0]:
        result += trapezoid(St+H[i][0],min(En-H[i][0],H[i][1]),H,i+1)
    if H[i][2] < En - H[i][0]: 
        result += trapezoid(max(St+H[i][0],H[i][2]),En-H[i][0],H,i+1)       
    return result

N = int(input())
t = inpl()
v = inpl()
H = [[v[0], 0, t[0]]]
for i in range(1,N):
    H.append([v[i], H[i-1][2], H[i-1][2]+t[i]])

H.append([float('inf'), 0, 0])
H.sort(key = lambda x: x[0])
for i in range(N,0,-1):
    H[i][0] -= H[i-1][0]    
print(trapezoid(0,sum(t), H, 0))

Submission status: Accepted

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

m = sum(t)
d = [0 for _ in range(m + 1)]

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

ans = 0
v = 0
s = m
for i in range(n - 1, -1, -1):
    for j in range(t[i]):
        d[s] = v
        if v == d[s - 1] and v < L[i]:
            ans += 0.25
        v = min(v + 1, L[i], d[s - 1])
        s -= 1

for i in range(1, m + 1):
    if d[i] == d[i - 1]:
        ans += d[i]
    elif d[i] > d[i - 1]:
        ans += d[i] - 0.5
    elif d[i] < d[i - 1]:
        ans += d[i] + 0.5
    #print(i, ans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
t = list(map(int,input().split()))
vlist = list(map(int,input().split()))
import numpy as np
t = np.cumsum(np.array(t))
T = t[-1]
def line(tl,tr,v):
    leq = np.arange(2*T+1)/2
    leq[:2*tl+1] *= -1
    leq[:2*tl+1] += tl
    leq[2*tl+1:2*tr+1] *= 0
    leq[2*tr+1:] -= tr
    leq += v
    return leq

f = np.zeros((N+2)*(2*T+1)).reshape((N+2,2*T+1))
for i in range(N):
    if i != 0:
        tl = t[i-1]
    else:
        tl = 0
    tr = t[i]
    v = vlist[i]
    f[i] = line(tl,tr,v)
f[N]=line(0,0,0)
f[N+1]=line(T,T,0)
v = f.min(0)

ans = 0
for i in range(len(v)-1):
    ans += v[i]+v[i+1]
ans *= 0.25
print(ans)

Submission status: Accepted

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


tt = 0
lim = []

for i in range(N):
    for j in range(ts[i]):
        lim.append(vs[i])
        tt += 1

up = [False for i in range(tt)]
v = 0
for i in range(tt):
    if lim[i] > v:
        v += 1
        lim[i] = v
        up[i] = True
    else:
        v = lim[i]

down = [False for i in range(tt)]
v = 0
for i in range(tt - 1, -1, -1):
    if lim[i] > v:
        v += 1
        if lim[i] > v:
            up[i] = False
        lim[i] = v
        down[i] = True
    else:
        v = lim[i]

ans = 0
for i in range(tt):
    ans += lim[i]
    if up[i] and down[i]:
        ans -= 0.75
    elif up[i] or down[i]:
        ans -= 0.5
    
print(ans)

Submission status: Accepted

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

t = [0] + t
for i in range(N):
    t[i + 1] += t[i]

y = [0] * (t[N] * 2 + 1)

for i, (t1, t2) in enumerate(zip(t, t[1:])):
    for x in range(2 * t1, 2 * t2):
        y[x + 1] = min(v[i], y[x] + 0.5)

y[2 * t[N]] = 0
for i, (t1, t2) in enumerate(zip(t[::-1], t[::-1][1:])):
    for x in range(2 * t1, 2 * t2, -1):
        y[x - 1] = min(y[x - 1], v[N - i - 1], y[x] + 0.5)

print(sum((y[i] + y[i + 1]) * 0.5 for i in range(t[N] * 2)) / 2)

Submission status: Accepted

Solution code:
N = int(input())
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))
 
maxv = [0] * (sum(ts) * 2 +1)
dp = [0] * (sum(ts) * 2 + 1)
ima = 1
for i in range(len(ts)):
  k = ts[i]
  if i != 0:
    maxv[ima-1] = min(vs[i],vs[i-1])
  for j in range(k*2):
    maxv[j+ima] = vs[i]
  ima  += k*2
maxv[-1] = 0
for i in range(1,len(dp)):
  dp[i] = min(dp[i-1] + 0.5,maxv[i])
for i in range(len(dp)-1,0,-1):
  dp[i-1] = min(dp[i] + 0.5,maxv[i-1],dp[i-1])
ans = sum(dp)/2
print(ans)

Submission status: Accepted

Solution code:
def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    a = []
    for i in t:
        a.append(i * 2)
    t = a
    v = list(map(int, input().split()))
    #print(t)
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    #print(speed_lim, len(speed_list), len(speed_lim))
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 0.5
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    #print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 0.5, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    #print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans / 2)
ABC076D()

Submission status: Accepted

Solution code:
def main():

    S = list(input())
    checklist = [0 for i in range(26)]
    for i in S:
        checklist[ord(i) - ord("a")] += 1
    ans = True

    for i in checklist:
        if i > 1:
            ans = False

    if not ans:
        print(-1)
        return 0
    else:
        ans = False
        for i in range(len(checklist)):
            if checklist[i] == 0:
                for i in S:
                    print(i, end="")
                print(chr(i + ord("a")), end = "")
                print()
                ans = True
                break

        if not ans:
            new_S = []
            for i in S:
                new_S.append(ord(i))

            for i in range(len(new_S) - 1):
                if new_S[i] > new_S[i + 1]:
                    for j in range(i - 1):
                        print(S[j], end = "")
                    print(chr(new_S[i - 1] + 1), end = "")
                    print()
                    ans = True
                    break

            if not ans:
                print(-1)
#main()

def ABC069D():

    H, W = map(int, input().split())
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(N):
        for j in range(a[i]):
            ans.append(i + 1)
    printlist = [[0 for i in range(W)] for j in range(H)]
    k = 0
    for i in range(H):
        for j in range(W):
            printlist[i][j] = ans[k]
            k += 1
        if i % 2 != 0:
            printlist[i] = printlist[i][::-1]

    for i in range(H):
        for j in range(W):
            print(printlist[i][j], end = "")
            if j != W:
                print(" ", end = "")
        print()
    print()
#ABC069D()

import math
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def ABC057D():

    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    v = sorted(v)[::-1]

    anslist = []
    for i in range(A, B + 1):

        anslist.append([sum(v[0:i]) / i, i, v[i - 1]])
    anslist.sort()
    anslist = anslist[::-1]
    ans = anslist[0][0]
    key = anslist[0][2]
    long = anslist[0][1]
    print(ans)
    for i in range(1, len(anslist)):
        if anslist[i][0] == anslist[i - 1][0]:
            ans = anslist[i][0]
            key = anslist[i][2]
            long = anslist[i][1]
        else:
            break
    #print(anslist)
    #print(ans, key, long)
    cnt = 0
    for i in v:
        if i == key:
            cnt += 1

    c = 0
    for i in v[:long]:
        #print(i)
        if i == key:
            c += 1
    #print(c, long)
    ans = 0
    if c == long:
        for i in range(A,  min(B + 1, cnt + 1)):
            ans += cc(cnt, i)
    else:
        ans = cc(cnt, c)
    #print(anslist)
    #print(cnt, c, long)
    print(ans)
#ABC057D()

def ABC104D():
    S = list(input())
    A_cnt = 0
    B_cnt = 0
    C_cnt = 0
    Q_cnt = 0
    ans = 0
    for i in S:
        if i == "A":
            A_cnt += 1
        elif i == "B":
            B_cnt += 1
        elif i == "C":
            C_cnt += 1
        else:
            Q_cnt += 1
    for i in range(Q_cnt + 1):
        for j in range(Q_cnt - i + 1):
            k = Q_cnt - i - j
            if A_cnt + i > 0 and B_cnt + j > 0 and C_cnt + k > 0:
                f_i = math.factorial(i)
                f_j = math.factorial(j)
                f_k = math.factorial(k)
                if f_i == 0:
                    f_i = 1
                if f_j == 0:
                    f_j = 1
                if f_k == 0:
                    f_k = 1
                ans += (A_cnt + i) * (B_cnt + j) * (C_cnt + k) * math.factorial(Q_cnt) // f_i // f_j // f_k
                print(ans, i, j, k, A_cnt + i, B_cnt + j, C_cnt + k)
                print(math.factorial(Q_cnt), f_i, f_j, f_k)
    print(ans)
#ABC104D()

def ARC073D():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

def ARC075():
    N, A, B = map(int, input().split())
    h = [int(input()) for i in range(N)]
    def enogth(T):
        import copy
        this_h = copy.copy(h)
        cnt = 0
        for i in range(N):
            this_h[i] -= B
            key = 0
            if this_h[i] > 0:
                key = this_h[i] / (A - B)
                if int(key) != key:
                    key += 1
                cnt += int(key)
        if cnt <= T:
            return True
        else:
            return False
    def sarch(i: object) -> object:
        print(i)
        if enogth(i):
            if i // 2 == 1:
                return i
            sarch(0 + i // 2)
        else:
            sarch(i + i // 2)
    print(sarch(10 ** 9))
#ARC075()

def ARC082D():
    N = int(input())
    p = list(map(int, input().split()))
    cnt = 0
    if p[N - 1] == N:
        #print(p[N - 1], N)
        p[-2], p[-1] = p[-1], p[-2]
        cnt += 1

    for i in range(N - 1):
        if p[i] == i + 1:
            p[i], p[i + 1] = p[i + 1], p[i]
            cnt += 1
    print(cnt)
#ARC082D()


from queue import Queue
def ABC070D():
    N = int(input())
    a, b, c =map(int, input().split())
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    x = [[] for i in range(N)]
    for i, j in xy:
        x[i - 1].append(j - 1)
        x[j - 1].append(i - 1)

    q = Queue()
    visited = [0 for i in range(N)]


def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    print(speed_lim)
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 1
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 1, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans)
#ABC076D()

def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    a = []
    for i in t:
        a.append(i * 2)
    t = a
    v = list(map(int, input().split()))
    #print(t)
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    #print(speed_lim, len(speed_list), len(speed_lim))
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 0.5
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    #print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 0.5, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    #print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans / 2)
ABC076D()

Submission status: Accepted

Solution code:
# ABC 076 D

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

e = sum(t)*2
vmax = [0 for k in range(e+2)]

s = 0
for k in range(N):
    for l in range(1,t[k]*2+1):
        vmax[s+l] = v[k]
    s += t[k]*2

hidari = [0 for k in range(e+1)]
for k in range(1,e+1):
    hidari[k] = min(hidari[k-1]+0.5,vmax[k])

migi = [0 for k in range(e+1)]
for k in range(1,e+1):
    migi[e-k] = min(migi[e-k+1]+0.5,vmax[e-k+1])

ans = 0
for k in range(e+1):
    ans += min(hidari[k],migi[k])
print(ans/2)

Submission status: Accepted

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

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

v_max = [0]    
idx = 0
for i in range(1, 2*sum(t)+1):
    time = i/2
    if time < t_cumsum[idx]:
        v_max.append(v[idx])
    elif time == t_cumsum[-1]:
        v_max.append(0)
    else:
        v_max.append(min(v[idx], v[idx+1]))
        idx += 1
# print(len(v_max), v_max)
    
vs = [0]*len(v_max)
for i in range(1, len(v_max)):
    vs[i] = min(vs[i-1]+0.5, v_max[i])
for i in range(len(v_max)-2, -1, -1):
    vs[i] = min(vs[i], vs[i+1]+0.5, v_max[i])
# print(vs)

ans = 0
for v0, v1 in zip(vs[:-1], vs[1:]):
    ans += (v0+v1)/2*0.5
print(ans)

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
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


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


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    end = 2 * sum(T)

    H = [INF] * (end + 10)
    now = 0
    for i, t in enumerate(T):
        for j in range(now, (now + t * 2) + 1):
            H[j] = min(H[j], V[i])
        now = now + t * 2

    H[0] = 0.0
    H[end] = 0.0
    for i in range(end):
        H[i + 1] = min(H[i + 1], H[i] + 1 / 2)
    for i in range(end, 0, -1):
        H[i - 1] = min(H[i - 1], H[i] + 1 / 2)

    ans = 0
    for i in range(end):
        ans += (H[i] + H[i + 1]) * 0.5 * (1/2)

    print(ans)


if __name__ == '__main__':
    main()

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
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


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


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    base = 2
    end = base * sum(T)

    H = [INF] * (end + 10)
    now = 0
    for i, t in enumerate(T):
        for j in range(now, (now + t * base) + 1):
            H[j] = min(H[j], V[i])
        now = now + t * base

    H[0] = 0.0
    H[end] = 0.0
    H[end + 1] = 0.0
    for i in range(end + 1):
        H[i + 1] = min(H[i + 1], H[i] + 1 / base)
    for i in range(end, 0, -1):
        H[i - 1] = min(H[i - 1], H[i] + 1 / base)

    # for i in range(len(H)):
    #     print(i, H[i])
    ans = 0
    pre_i, pre_mode = 0, 1
    for i in range(end + 1):
        if H[i] < H[i + 1]:
            mode = 0
        elif H[i] == H[i + 1]:
            mode = 1
        else:
            mode = 2

        if mode != pre_mode:
            # print(pre_i, i, (H[pre_i] + H[i]) * ((i - pre_i) / base) * (1/2))
            ans += (H[pre_i] + H[i]) * ((i - pre_i) / base) * (1/2)
            pre_i, pre_mode = i, mode

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Solution code:
'''
38分あたり
https://www.youtube.com/watch?v=T1zXzsoK268
'''
def input_num_list(): return list(map(int, input().split()))

n = int(input())
t = input_num_list()
T = sum(t)
v = input_num_list()
maxv = [100 for _ in range(2 * T + 1)]
maxv[0] = 0
maxv[2 * T] = 0

t_l, t_r = 0, 0
for i in range(n):
    t_l = t_r
    t_r += t[i]
    vv = v[i]
    for j in range(2 * t_l, 2 * t_r + 1):
        maxv[j] = min(maxv[j], vv)

#print(maxv)
i = 1
while i <= 2 * T:
    maxv[i] = min(maxv[i], maxv[i - 1] + 0.5)
    i += 1
#print(maxv)
i = 2 * T - 1
while i >= 0:
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)
    i -= 1
#print(maxv)
ans = 0
i = 0
while i <= 2 * T - 1:
    ans += 0.25 * (maxv[i] + maxv[i + 1])
    i += 1
    
print(ans)
#print(maxv)

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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, T, V):

    T.append(0)
    V.append(0)

    df = 0.5
    # t, v
    vs = [0] * int(sum(T)*(1/df) + 2)

    i = 1
    for t, v in zip(T, V):
        # error_print(vs)
        if vs[i-1] > v:
            j = 0
            while abs(vs[i-1-j] - vs[i-1-j+1]) > 0.001:
                vs[i-1-j] = min(vs[i-1-j], v + j*df)
                j += 1

        for _ in range(t*int(1/df)):
            vs[i] = min(vs[i-1]+df, v)
            i += 1

    ans = 0
    for i in range(len(vs)-1):
        d = vs[i+1] - vs[i]
        ans += vs[i]*df
        ans += (d*df)/2

    # print('\t'.join(map(lambda x: str(x[1]),
    #                     filter(lambda x: x[0] % 2 == 0, zip(range(len(vs)), vs))))
    #       )
    return ans


def main():
    N = read_int()
    T = read_int_n()
    V = read_int_n()

    print(slv(N, T, V))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
T = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]
T.append(0)
V.append(0)
Vt = [0 for i in range(N + 1)]
r = sum(T)
R = [0 for i in range(N)]
for i in range(N - 1):
  r -= T[i]
  R[i] = r
for i in range(N - 1, -1, -1):
  Vt[i] = min(V[i], V[i + 1], Vt[i + 1] + T[i + 1])
L = 0
v0 = 0
for i in range(N):
  ta = min(V[i] - v0, (T[i] - (v0 - Vt[i])) / 2, T[i])
  tb = max(v0 + ta - Vt[i], 0)
  L += (2 * v0 + ta) * ta / 2 + (v0 + ta) * (T[i] - ta - tb) + (2 * (v0 + ta) - tb) * tb / 2
  v0 = v0 + ta - tb
print(L)

Submission status: Accepted

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 = [[] for i in range(N + 2)]
for i, (v, l, r) in enumerate(zip(vs + [0, 0], [0] + accTs[:-1] + [0, sumT], accTs + [0, sumT])):

    vms = [v + l - t / 2 for t in range(0, l * 2)] + \
          [v] * ((r - l) * 2 + 1) + \
          [v + t / 2 - r for t in range(r * 2 + 1, sumT * 2 + 1)]

    vMaxs[i] = vms

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

print(sum(vMaxs) / 2)

Submission status: Accepted

Solution code:
from bisect import bisect_left
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 = t[-1],0
for i in range(2*T+1):
	num = min(i/2,T-i/2)
	for j in range(max(0,bisect_left(t,i/2-100)-1),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)