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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
T=[0]+list(map(lambda x:int(x)*2,input().split()))+[0]
V=[0]+list(map(lambda x:int(x)*2,input().split()))+[0]
v=[INF]*(sum(T)+1)
def f(v,l,r,t):
    if t<l:
        return v+(l-t)
    elif l<=t<r:
        return v
    else:
        return v+(t-r)
t=0
for i in range(N+2):
    for j in range(len(v)):
        v[j]=min(v[j],f(V[i],t,t+T[i],j))
    t+=T[i]
ans=0
for i in range(len(v)-1):
    ans+=v[i]+v[i+1]
ans/=8
print(ans)

Submission status: Accepted

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

vmax_l = [0 for _ in range(2*T+1)]
vmax_r = [0 for _ in range(2*T+1)]
vmax = [0 for _ in range(2*T+1)]
for i in range(1, 2*T+1):
    tt = 0
    for j in range(n):
        if i > tt+t[j]*2:
            tt += t[j]*2
        else:
            vmax_l[i] = min(v[j], vmax_l[i-1]+0.5)
            break
for i in range(2*T-1, -1, -1):
    tt = 2*T
    for j in range(n-1, -1, -1):
        if i < tt-t[j]*2:
            tt -= t[j]*2
        else:
            vmax_r[i] = min(v[j], vmax_r[i+1]+0.5)
            break
for i in range(2*T+1):
    vmax[i] = min(vmax_l[i], vmax_r[i])

point_t = [0]
point_v = [0]
for i in range(1, 2*T):
    if vmax[i-1] != vmax[i] or vmax[i] != vmax[i+1]:
        point_t.append(i)
        point_v.append(vmax[i])
point_t.append(2*T)
point_v.append(0)

ans = 0
for i in range(1, len(point_t)):
    ans += (point_t[i]-point_t[i-1])*(point_v[i]+point_v[i-1])/4
print(ans)

Submission status: Accepted

Solution code:
n,*L=map(int,open(0).read().split())
T,V=L[:n],L[n:]
s=sum(T)
a=[0]
for t,v1,v2 in zip(T,V,V[1:]+[0]):
	a+=[v1]*(2*t-1)+[min(v1,v2)]
for i in range(2*s):
	a[i+1]=min(a[i+1],a[i]+.5)
for i in range(2*s,0,-1):
	a[i-1]=min(a[i-1],a[i]+.5)
print(sum(a)/2)

Submission status: Accepted

Solution code:
class ConvexHullTrick():
    def __init__(self, xlist, INF=10**18):
        xlist = sorted(xlist)
        self.comp = {x : k for k, x in enumerate(xlist)}
        self.h = (len(xlist) - 1).bit_length()
        self.n = 2**self.h
        self.ie = (0, INF)
        self.inf = INF
        self.x = xlist + [INF] * (self.n - len(xlist))
        self.tree = [self.ie for _ in range(2 * self.n)]

    def val(self, line, x):
        a, b = line
        return a * x + b

    def _add_(self, line, idx, lt, rt):
        while True:
            mid = (lt + rt) // 2
            lx = self.x[lt]
            mx = self.x[mid]
            rx = self.x[rt - 1]
            lu = self.val(line, lx) < self.val(self.tree[idx], lx)
            mu = self.val(line, mx) < self.val(self.tree[idx], mx)
            ru = self.val(line, rx) < self.val(self.tree[idx], rx)
            if lu and ru:
                self.tree[idx] = line
                return
            if not lu and not ru:
                return
            if mu:
                self.tree[idx], line = line, self.tree[idx]
            if lu != mu:
                rt = mid
                idx = 2 * idx
            else:
                lt = mid
                idx = 2 * idx + 1

    def add_line(self, line):
        self._add_(line, 1, 0, self.n)

    def add_seg(self, line, lt, rt):
        lidx = self.comp[lt] + self.n
        ridx = self.comp[rt] + self.n
        lt = self.comp[lt]
        rt = self.comp[rt]
        size = 1
        while ridx - lidx > 0:
            if lidx & 1:
                self._add_(line, lidx, lt, lt + size)
                lidx += 1
                lt += size
            if ridx & 1:
                ridx -= 1
                rt -= size
                self._add_(line, ridx, rt, rt + size)
            lidx >>= 1
            ridx >>= 1
            size <<= 1

    def get_min(self, x):
        idx = self.comp[x] + self.n
        res = self.inf
        while idx:
            res = min(res, self.val(self.tree[idx], x))
            idx >>= 1
        return res

N = int(input())
T = list(map(int, input().split()))
V = [0] + list(map(int, input().split())) + [0]
X = [0]

for i in range(N):
    X.append(X[-1] + 2 * T[i])

cht = ConvexHullTrick(range(X[-1] + 2))

for i in range(N):
    cht.add_seg((0, 2 * V[i + 1]), X[i], X[i + 1] + 1)

for i in range(N):
    cht.add_seg((1, 2 * V[i] - X[i]), X[i], X[-1] + 1)

for i in range(N):
    cht.add_seg((-1, 2 * V[i + 2] + X[i + 1]), X[0], X[i + 1] + 1)

D = [0 for _ in range(X[-1] + 1)]

for i in range(X[-1] + 1):
     D[i] = cht.get_min(i)

S = 0

for i in range(X[-1]):
    S += D[i] * 2 + (D[i + 1] - D[i])

print(S / 8)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
FT = sum(T)*2+1
import numpy as np
limit = []
cumt = 0
for n in range(2+N):
    if n==0:
        lis = [(0.5)*i for i in range(FT)]
    elif n==1:
        lis = [(0.5)*i for i in range(FT)][::-1]
    else:
        t = T[n-2]
        v = V[n-2]
        lis = [v+cumt//2-0.5*i for i in range(cumt)] + [v for _ in range(t*2)] + [v+i*0.5 for i in range(FT-cumt-t*2)]
        cumt += t*2
    limit.append(lis)
limit = np.min(np.array(limit), axis=0)
ans = 0
for i in range(FT-1):
    ans += (limit[i+1]+limit[i])*0.25
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    T = [t * 2 for t in T]
    V = [v * 2 for v in V]
    Tall = sum(T)
    R = [0] * (Tall + 1)
    j = N - 1
    tc, vc, vn = T[-1], V[-1], V[-1]
    R[-1] = 0
    for i in reversed(range(Tall)):
        tc -= 1
        if tc == 0:
            j -= 1
            tc, vn = T[j], V[j]
        R[i] = min(R[i + 1] + 1, vc, vn)
        vc = vn
    v = 0
    d = 0.0
    j = 0
    tc, vc, vn = T[j], V[j], V[j]
    T.append(0)
    V.append(0)
    for i in range(1, Tall + 1):
        tc -= 1
        if tc == 0:
            j += 1
            tc, vn = T[j], V[j]
        vnn = min(v + 1, R[i], vc, vn)
        d += (v + vnn) / 2
        vc = vn
        v = vnn
    print(d / 4)

main()

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 076
# D - AtCoder Express
# https://atcoder.jp/contests/abc076/tasks/abc076_d


def solve(T, V, velocity):
    accT = 1
    for t, max_v in zip(T, V):
        for i in range(accT, accT+2*t):
            velocity[i] = min(velocity[i], velocity[i-1]+0.5, max_v)
        accT += 2*t


def main():

    N, *A = map(int, open(0).read().split())
    T = A[:N]
    V = A[N:]

    INF = 10**10

    velocity = [INF]*(sum(T)*2+1)
    velocity[0] = 0
    velocity[-1] = 0
    solve(T, V, velocity)
    velocity = velocity[::-1]
    solve(T[::-1], V[::-1], velocity)

    ans = 0
    pre_v = velocity[0]
    for v in velocity[1:]:
        ans += (pre_v + v) * 0.25
        pre_v = v

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())
T = [0] + list(map(int, input().split()))
V = [0] + list(map(int, input().split()))

left = [0] * (N + 1)
right = [0] * (N + 1)

for i in range(1, N):
    start = left[i - 1]
    left[i] = min(start + T[i], V[i], V[i + 1])

for i in range(N - 1, 0, -1):
    start = right[i + 1]
    right[i] = min(start + T[i + 1], V[i], V[i + 1])

total = [min(left[i], right[i]) for i in range(N + 1)]
ans = 0
for i in range(1, N + 1):
    x = (V[i] - total[i - 1]) + (V[i] - total[i])
    if x >= T[i]:
        V[i] = (total[i - 1] + T[i] + total[i]) / 2
        x = T[i]
    d =(total[i - 1] + V[i]) * (V[i] - total[i - 1]) / 2 #台形左側
    d += (total[i] + V[i]) * (V[i] - total[i]) / 2 #台形右側
    d += V[i] * (T[i] - x) #真ん中の定速部分

    ans += d

print (ans)

Submission status: Accepted

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

vel_go=[0]
for ti, v_lim in zip(T,V):
    for _ in range(ti*2):
        v = min(vel_go[-1] + 0.5, v_lim)
        vel_go.append(v)

vel_back = [0]
for ti, v_lim in zip(T[::-1], V[::-1]):
    for _ in range(ti*2):
        v = min(vel_back[-1] + 0.5, v_lim)
        vel_back.append(v)
vel_back.reverse()

velocity = tuple(min(x,y) for x, y in zip(vel_go, vel_back))
ans = sum(0.25*(x+y) for x,y in zip(velocity[:-1], velocity[1:]))
print(ans)

Submission status: Accepted

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

vel_go = [0]
for ti, v_lim in zip(T, V):
    for _ in range(ti * 2):
        v = min(vel_go[-1] + 0.5, v_lim)
        vel_go.append(v)

vel_back = [0]
for ti, v_lim in zip(T[::-1], V[::-1]):
    for _ in range(ti * 2):
        v = min(vel_back[-1] + 0.5, v_lim)
        vel_back.append(v)
vel_back.reverse()

velocity = tuple(min(x, y) for x, y in zip(vel_go, vel_back))
ans = sum(0.25*(x+y) for x, y in zip(velocity[:-1], velocity[1:]))
print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

def dist(i, j, lim, t):
	if abs(i - j) > t:
		dist = -INF
	else:
		x = (t + j - i) / 2
		y = (t + j + i) / 2
		if  y <= lim:
			dist = (i + y) * x / 2 + (j + y) * (t - x) / 2
		else:
			dist = (i + lim) * (lim - i) / 2 + lim * (t - (lim - i) - (lim - j)) + (j + lim) * (lim - j) / 2
			# print(dist)

	return dist

#処理内容
def main():
	N = int(input())
	T = getlist()
	V = getlist()
	DP = [[-INF] * 101 for i in range(N + 1)]
	DP[0][0] = 0
	for i in range(N - 1):
		lim = V[i]
		t = T[i]
		for p in range(lim + 1):
			for q in range(lim + 1):
				d = dist(p, q, lim, t)
				DP[i + 1][q] = max(DP[i + 1][q], DP[i][p] + d)

	lim = V[-1]
	t = T[-1]
	for p in range(lim + 1):
		d = dist(p, 0, lim, t)
		DP[N][0] = max(DP[N][0], DP[N - 1][p] + d)


	print(DP[N][0])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())
T = [0] + list(map(int, input().split()))
V = [0] + list(map(int, input().split()))

max_speed_from_left = [0] * (N + 1)
max_speed_from_right = [0] * (N + 1)

for i in range(1, N):
    start = max_speed_from_left[i - 1]
    max_speed_from_left[i] = min(start + T[i], V[i], V[i + 1])

for i in range(N - 1, 0, -1):
    start = max_speed_from_right[i + 1]
    max_speed_from_right[i] = min(start + T[i + 1], V[i], V[i + 1])

speed = [min(x, y) for x, y in zip(max_speed_from_left, max_speed_from_right)]

def dist(left_speed, right_speed, t, v):
    x = (v - left_speed) + (v - right_speed)
    if x >= t:
        v = (left_speed + right_speed + t) / 2
        x = t
    d = (left_speed + v) * (v - left_speed) / 2
    d += v * (t - x)
    d += (right_speed + v) * (v - right_speed) / 2
    return d

ans = 0
for i in range(1, N + 1):
    ans += dist(speed[i - 1], speed[i], T[i], V[i])

print (ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
end = [-1]*N
end[-1] = 0

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

ans = 0
s = 0

for i in range(N):
    e = end[i]

    if s+t[i]<=e:
        ans += (s+s+t[i])*t[i]/2
        s = s+t[i]
    else:
        up = min(v[i], (s+e+t[i])/2)
        ans += (s+up)*(up-s)/2
        ans += (e+up)*(up-e)/2
        ans += up*(t[i]-(up-s)-(up-e))
        s = e

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))
s = [0]*n
for i in range(n-1):
    s[i+1] = s[i] + T[i]
l = (s[-1]+T[n-1])*2+1
ans = [1e100]*l

for i in range(l):
    ans[i] = min(ans[i],i/2)
    ans[l-i-1] = min(ans[i],i/2)

for j in range(n):
    for i in range(l):
        if i <= s[j]*2:
            ans[i] = min(ans[i], V[j]+(s[j]*2-i)/2)
        elif s[j]*2 <= i <= s[j]*2+T[j]*2:
            ans[i] = min(ans[i],V[j])
        else:
            ans[i] = min(ans[i],V[j]+(i-s[j]*2-T[j]*2)/2)
anser = 0
for i in range(l-1):
    anser += (ans[i]+ans[i+1])/4
print(anser)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
u=list(map(int,input().split()))
speed=[0]
for i in range(n):
  speed+=[u[i]]*t[i]*2
speed.append(0)
m=len(speed)
for i in range(1,m):
  speed[i-1]=min(speed[i-1],speed[i])
del speed[-1]
m-=1
for i in range(1,m):
  speed[i]=min(speed[i],speed[i-1]+0.5)
for i in range(m-2,-1,-1):
  speed[i]=min(speed[i],speed[i+1]+0.5)
ans=0
for i in range(1,m):
  ans+=abs(speed[i-1]+speed[i])*0.25
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
M = 2
dt = 1 / M
R = sum(T)

maxSpeeds = [10**18] * (R * M + 1)
now = 0
for t, v in zip(T, V):
    for i in range(t * M + 1):
        maxSpeeds[now + i] = min(maxSpeeds[now + i], v)
    now += t * M

maxSpeeds[0] = 0
maxSpeeds[-1] = 0
for t in range(1, R * M + 1):
    maxSpeeds[t] = min(maxSpeeds[t - 1] + dt, maxSpeeds[t])
    maxSpeeds[-(t + 1)] = min(maxSpeeds[-t] + dt, maxSpeeds[-(t + 1)])

ans = 0
for l, r in zip(maxSpeeds, maxSpeeds[1:]):
    ans += (l + r) / M / 2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = [int(a) * 2 for a in input().split()]
V = [int(a) * 2 for a in input().split()]
MA = [0] * (sum(T) + 1)
a = 0
for i in range(N):
    for j in range(T[i]):
        a += 1
        MA[a] = min(MA[a-1] + 1, V[i])
MA[a] = 0
for i in range(N)[::-1]:
    for j in range(T[i]):
        a -= 1
        MA[a] = min(MA[a], MA[a+1] + 1, V[i])

print((sum(MA[1:]) + sum(MA[:-1])) / 8)

Submission status: Accepted

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

l = sum(T) * 2 + 1
t_cond = [0] + T + [0]
v_cond = [0] + V + [0]
memo = [[0] * l for _ in range(N + 2)]
left = 0
for i in range(N + 2):
    for j in range(l):
        if j < left:
            memo[i][j] = v_cond[i] + (left - j) * 0.5
        elif left <= j <= left + t_cond[i] * 2:
            memo[i][j] = v_cond[i]
        else:
            memo[i][j] = v_cond[i] + (j - left - t_cond[i] * 2) * 0.5
            
    # Shift lower bound
    left += t_cond[i] * 2

f = [min(memo[i][j] for i in range(N + 2)) for j in range(l)]
ans = 0
for i in range(l - 1):
    ans += 0.25 * (f[i] + f[i + 1])
print(ans)

Submission status: Accepted

Solution code:
def calc_vt(v,t):
    vt = [0]*(sum(t)*2+1)
    t_sum = 0
    for ti,vi in zip(t,v):
        for i in range(ti*2):
            vt[t_sum + 1 + i] = min(vt[t_sum + i] + 0.5,vi)
        t_sum += ti*2
    return vt

n = input().split()
tn = list(map(int,input().split()))
vn = list(map(int,input().split()))

vt_l = calc_vt(vn,tn)
vt_r = calc_vt(vn[::-1],tn[::-1])[::-1]

vt_lr = [min(vl,vr) for vl,vr in zip(vt_l,vt_r)]

print(sum((a+b)*0.5/2 for a,b in zip(vt_lr,vt_lr[1:])))

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
# from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

t.append(0)
v.append(0)
t.insert(0,0)
v.insert(0,0)

tt=sum(t)
lst=[0]*(tt*2+1)

for i in range(tt*2-1):
    tmp=[]
    now=0.5+i/2
    cnt=0
    for j in range(n+2):
        l=cnt
        cnt+=t[j]
        r=cnt
        if j==n+1:
            l=r
        if now<=l:
            tmp.append(l-now+v[j])
        elif r<=now:
            tmp.append(now-r+v[j])
        else:
            tmp.append(v[j])
        # print(l,r)
    lst[i+1]=min(tmp)

# print(lst)
ans=0
for i in range(tt*2):
    ans+=0.25*(lst[i+1]+lst[i])
print(ans)

Submission status: Accepted

Solution code:
# solution

import io
import math
import scipy.sparse
import numpy

data = int(input())

array1 = list(map(lambda x:int(x)*2,input().split()))

array2 = list(map(lambda x:int(x)*2,input().split()))

sumt = sum(array1)

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

counter = 0

for t,v in zip(array1,array2):
    for i in range(counter,counter+t+1):
        maxv[i] = min(maxv[i], v)
    counter += 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:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 切り替えポイントで出せる速度：両側から見てminを取る
# あとは中を構成する

N = I()
t = LI()
v = [0] + LI() + [0]

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

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

A = [0]*(N+1)
for i in range(N+1):
    A[i] = min(L[i],R[i])

ans = 0
for i in range(1,N+1):
    if A[i-1] >= A[i]:
        x = (t[i-1]-A[i-1]+A[i])/2
        if A[i-1]+x <= v[i]:
            ans += (A[i-1]+x/2) * x \
                     + (A[i-1]+x+A[i])/2 * (x+A[i-1]-A[i])
        else:
            ans += (A[i-1]+v[i])/2 * (v[i]-A[i-1]) \
                     + v[i] * (t[i-1]-2*v[i]+A[i-1]+A[i]) \
                     + (v[i]+A[i])/2 * (v[i]-A[i])
    else:
        x = (t[i-1]-A[i]+A[i-1])/2
        if A[i]+x <= v[i]:
            ans += (A[i]+x/2) * x \
                     + (A[i]+x+A[i-1])/2 * (x+A[i]-A[i-1])
        else:
            ans += (A[i-1]+v[i])/2 * (v[i]-A[i-1]) \
                     + v[i] * (t[i-1]-2*v[i]+A[i-1]+A[i]) \
                     + (v[i]+A[i])/2 * (v[i]-A[i])

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N = int(input())
t = list(accumulate([0] + list(map(int, input().split())) + [0]))
v = [0] + list(map(int, input().split())) + [0]
prev = 0
ans = 0
T = t[-1]
for i in range(0, 2*T+1):
    i /= 2
    cur = i
    for j in range(N+1):
        l = t[j]
        r = t[j+1]
        u = v[j+1]
        if i < l:
            cur = min(cur, u + (l - i))
        elif i > r:
            cur = min(cur, u + (i - r))
        else:
            cur = min(cur, u)
    ans += (prev + cur) / 4
    prev = cur
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
trng = [0]+list(map(int,input().split()))+[0]
vlim = [0]+list(map(int,input().split()))+[0]
n += 2
smt = sum(trng)
table = [[-1 for i in range(smt*2+1)] for j in range(n)]
acc = 0
for i in range(n):
  if i == 0:
    for j in range(smt*2+1):
      table[i][j] = j/2
  elif i == n-1:
    for j in range(smt*2+1):
      table[i][j] = smt-table[0][j]
  else:
    v = vlim[i]
    t = trng[i]
    for j in range(acc):
      table[i][j] = v+(acc-j)/2
    for j in range(acc,acc+t*2+1):
      table[i][j] = v
    acc += t*2
    for j in range(acc+1,smt*2+1):
      table[i][j] = v+(j-acc)/2
ans = 0
ansls = list(zip(*table))
for arr in ansls:
  ans += min(arr)*0.5
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
runtime = sum(t)
speed = [0] * (runtime*2+1)
now_t, now_v = 0,0
for ti,vi in zip(t,v):
  for i in range(now_t*2+1,now_t*2+ti*2+1):
    next_v = min(now_v+0.5, vi)
    speed[i] = next_v
    now_v = next_v
  now_t += ti
speed[-1] = 0
now_t, now_v = runtime,0
for ti,vi in zip(t[::-1],v[::-1]):
  for i in range(now_t*2-1,now_t*2-ti*2-1,-1):
    next_v = min([now_v+0.5, speed[i],vi])
    speed[i] = next_v
    now_v = next_v
  now_t -= ti
ans = 0
for i in range(runtime*2):
  ans += speed[i]+speed[i+1]
ans /= 4
print(ans)

Submission status: Accepted

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

unit = 2

acumT = [0] * (n + 1)
for i in range(n):
  acumT[i+1] = acumT[i] + T[i+1]
  
PV = [0] * (sum(T) * unit + 1)
for p in range(1, n + 1):
  t1 = acumT[p-1]
  t2 = acumT[p]
# for (t1, t2), (v1, v2, v3) in zip(zip(acumT, acumT[1:]), zip(V, V[1:], V[2:])):
  for i in range(t1 * unit, t2 * unit + 1):
    ii = i / unit 
    PV[i] = min([ii - acumT[k] + V[k] for k in range(0, p)] + [V[p]] + [-ii + acumT[m] + V[m+1] for m in range(p, n+1)])

area = sum((i + j) / unit / 2 for i, j in zip(PV, PV[1:]))  
print(area)

Submission status: Accepted

Solution code:
n=int(input())
t=[int(a)*2 for a in input().split()]
v=[int(a)*2 for a in input().split()]
ma=[0]*(sum(t)+1)
a=0
for i in range(n):
  for j in range(t[i]):
    a+=1
    ma[a]=min(ma[a-1]+1,v[i])
ma[a]=0
for i in range(n)[::-1]:
  for j in range(t[i]):
    a-=1
    ma[a]=min(ma[a],ma[a+1]+1,v[i])
print((sum(ma[1:])+sum(ma[:-1]))/8)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      if a>100:
        break
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(lambda t: int(t) * 10, input().split()))
V = list(map(int, input().split())) + [0]
R = sum(T)

maxSpeed = [10**18] * (R + 1)
maxSpeed[0] = 0
maxSpeed[R] = 0
now = 0
for i, t in enumerate(T):
    now += t
    maxSpeed[now] = min(V[i], V[i + 1])

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

for t in range(1, R + 1):
    maxSpeed[t] = min(maxSpeed[t], maxSpeed[t - 1] + 0.1)
for t in range(R)[::-1]:
    maxSpeed[t] = min(maxSpeed[t], maxSpeed[t + 1] + 0.1)

base = 0
upper = 0
for v1, v2 in zip(maxSpeed, maxSpeed[1:]):
    base += min(v1, v2)
    upper += abs(v1 - v2)
ans = base + upper / 2
print(ans / 10)

Submission status: Accepted

Solution code:
# 写経AC
N = int(input())
T = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]

Ts = sum(T)

# Vmax[t]: t秒での最大速度 (0.5秒間隔)
Vmax = [float("inf")] * (Ts * 2 + 1)

ts = 0
for i in range(N):
    for t in range(T[i]):
        t1 = (ts + t) * 2
        t2 = (ts + t) * 2 + 1
        Vmax[t1] = min(Vmax[t1], V[i])
        Vmax[t2] = min(Vmax[t2], V[i])

    # 時間の区切りの部分は閉区間が重なっている
    Vmax[(ts + T[i]) * 2] = min(Vmax[(ts + T[i]) * 2], V[i])

    ts += T[i]

# 0秒とT秒
Vmax[0] = Vmax[Ts * 2] = 0
# 左から右に
for t in range(Ts * 2):
    Vmax[t + 1] = min(Vmax[t + 1], Vmax[t] + 0.5)
# 右から左に
for t in range(Ts * 2 - 1, 0, -1):
    Vmax[t] = min(Vmax[t], Vmax[t + 1] + 0.5)

ans = 0.0
for i in range(Ts * 2):
    # 台形の公式
    ans += (Vmax[i] + Vmax[i + 1]) * 0.5 / 2

print(ans)

Submission status: Accepted

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

ST = [0] * (N + 1)
for i in range(N):
    ST[i + 1] = ST[i] + T[i]

V2 = [0] * N
for i in range(N):
    V2[i] = V1[i + 1] + ST[i + 1]
z = V2[-1]
for i in range(N - 1, -1, -1):
    if V2[i] > z:
        V2[i] = z
    else:
        z = V2[i]


Vmax = [0] * (ST[-1] * 2 + 1)
j = 0
t = 0
for i, Tn in enumerate(ST):
    while t < Tn or j == 0:
        Vmax[2 * t + j] = min(V1[i - 1], V2[i - 1])
        V2 = [x - 0.5 for x in V2]
        t += j
        j ^= 1

v, cnt = 0, 0
for i in range(ST[-1] * 2):
    nVmax = Vmax[i + 1]
    nv = min(v + 0.5, nVmax)
    cnt += (v + nv) * 0.5 / 2
    v = nv

print(cnt)

Submission status: Accepted

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

speed = [10 ** 9] * (2 * time + 1)
limit = [10 ** 9] * (2 * time + 1)

i = 0
for j, k in zip(t, v):
    for _ in range(j * 2):
        limit[i] = min(limit[i], k)
        i += 1
    limit[i] = min(limit[i], k)

s = 0
for i in range(2 * time + 1):
    s = min(s, limit[i])
    speed[i] = min(speed[i], s)
    s += 0.5
s = 0
for i in reversed(range(2 * time + 1)):
    s = min(s, limit[i])
    speed[i] = min(speed[i], s)
    s += 0.5

dist = 0
for i in range(2 * time):
    dist += (speed[i] + speed[i + 1]) / 4
print(dist)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, t: "List[int]", v: "List[int]"):
    bounds = [[] for _ in range(N)]
    gb0 = (1, 0)
    tend = sum(t)
    gb1 = (-1, tend)
    for i in range(N):
        bounds[i].append(gb0)
        bounds[i].append(gb1)
    stt = 0
    for i in range(N):
        ti = t[i]
        vi = v[i]
        end = stt + ti
        b0 = (-1, stt + vi)
        b1 = (0, vi)
        b2 = (1, -end + vi)
        for j in range(i):
            bounds[j].append(b0)
        bounds[i].append(b1)
        for j in range(i + 1, N):
            bounds[j].append(b2)
        stt = end
    stt = 0
    vms = [0] * (tend * 2 + 1)
    for i in range(N):
        end = stt + t[i]
        bi = bounds[i]
        inf = float("inf")
        mins = {-1: inf, 0: inf, 1: inf}
        for a, b in bi:
            mins[a] = min(mins[a], b)
        for tm in range(stt * 2, end * 2):
            vms[tm] = min(a * tm + b * 2 for a, b in mins.items())
        stt = end
    print(sum(vms) / 4)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    t = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    v = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, t, v)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n=int(input())
inf=10000000000000
ans=[[-1,-1] for i in range(n)]
ans[-1][1],ans[0][0]=0,0
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v2=[]
for i in range(n):
    heapq.heappush(v2,(v[i],i))

def next(y,wh):
    global ans,n
    ansi=inf
    if wh:
        r1,r2=range(y[1]-1,-1,-1),range(y[1],n)
    else:
        r1,r2=range(y[1],-1,-1),range(y[1]+1,n)
    now=0
    for j in r1:
        if ans[j][1]!=-1:
            ansi=min(ansi,ans[j][1]+now)
        now+=t[j]
        if ans[j][0]!=-1:
            ansi=min(ansi,ans[j][0]+now)
    now=0
    for j in r2:
        if ans[j][0]!=-1:
            ansi=min(ansi,ans[j][0]+now)
        now+=t[j]
        if ans[j][1]!=-1:
            ansi=min(ansi,ans[j][1]+now)  
    if wh:
        ans[y[1]][0]=min(ansi,y[0])
        ans[y[1]-1][1]=ans[y[1]][0]
    else:
        ans[y[1]][1]=min(ansi,y[0])
        ans[y[1]+1][0]=ans[y[1]][1]  

for i in range(n):
    y=heapq.heappop(v2)
    if ans[y[1]][0]==-1:next(y,True)
    if ans[y[1]][1]==-1:next(y,False)
answer=0
for i in range(n):
    h=min((t[i]+sum(ans[i]))/2,v[i])
    answer+=((h**2-ans[i][0]**2)/2)
    answer+=((h**2-ans[i][1]**2)/2)
    answer+=(h*(t[i]+sum(ans[i])-2*h))
print(answer)