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:
n = int(input())

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

time = sum(tt);

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

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

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0
v_list = []

# print (border)
while t < time :
	v_list = []
	t += 0.5

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

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

	v0 = min(v_list)
#	print(v0)

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

ans /= 4.0
print (ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

time = sum(tt);

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

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

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

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

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

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

#	print(v0)

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

ans /= 4.0
print (ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

time = sum(tt);

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

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

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

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

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

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

#	print(v0)

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

print (ans)

Submission status: Time Limit Exceeded

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

durs = [0]
for i in range(N):
    durs.append(durs[-1] + ts[i])
T = durs[-1]

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

for i in range(N):
    t1,t2 = durs[i],durs[i+1]
    for ti in range(2*T + 1):
        t = ti*0.5
        if t < t1:
            maxv[ti] = min(maxv[ti], vs[i] + (t1-t))
        elif t > t2:
            maxv[ti] = min(maxv[ti], vs[i] + (t-t2))
        else:
            maxv[ti] = min(maxv[ti], vs[i])

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

Submission status: Time Limit Exceeded

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


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

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

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

t_idx = 0

t_tot = sum(ts)

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


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

time = sum(tt);

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

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

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

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

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

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

#	print(v0)

	ans += (vlast + v0)
	vlast = v0

ans /= 4.0
print (ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

time = sum(tt);

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

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

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

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

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

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

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

print (ans)

Submission status: Time Limit Exceeded

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


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

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

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

t_idx = 0

t_tot = sum(ts)

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


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

time = sum(tt);

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

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

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

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

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

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

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


print (ans)

Submission status: Memory Limit Exceeded

Solution code:
ADJ = 10**3
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
for i in range(n):
    ts[i] *= ADJ
    vs[i] *= ADJ
tt = sum(ts)
vss = [0]*tt
j = 0
cnt = 0
for i in range(tt):
    vss[i] = vs[j]
    cnt += 1
    if cnt == ts[j]:
        j += 1
        cnt = 0
#print(vss)
max_speed = 1
max_speeds = [0]*tt
for i in reversed(range(tt-1)):
    max_speeds[i] = min(max_speed,vss[i],vss[i+1],max_speeds[i+1]+1)
    max_speed += 1
#print(max_speeds)
cv = 0
for i in range(tt):
    if cv < max_speeds[i]:
        cv += 1
    elif cv == max_speeds[i]:
        pass
    else:
        cv -= 1
    vss[i] = cv
#print(vss)
res = 0
for i in range(tt):
    if i == 0:
        res += vss[i] / 2
    else:
        if vss[i] >= vss[i-1]:
            res += vss[i-1] + (vss[i] - vss[i-1]) / 2
        else:
            res += (vss[i-1] - vss[i]) / 2 + vss[i]
    #print()
    #print(str(i)+" "+str(res))
print(res/ADJ/ADJ)

Submission status: Accepted

Solution code:
import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random
#Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#Prime-Factorize
def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res
#nCr
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
#拡張Euclidの互除法
def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g
#BIT
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res
#Associative Array
class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)
#Floor Sum
def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
#Z-Algorithm
def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(self.s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and self.s[i - j] == self.s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
#mod-sqrt
def mod_sqrt(a, p):
    if a == 0:
        return 0
    if p == 2:
        return 1
    k = (p - 1) // 2
    if pow(a, k, p) != 1:
        return -1
    while True:
        n = random.randint(2, p - 1)
        r = (n ** 2 - a) % p
        if r == 0:
            return n
        if pow(r, k, p) == p - 1:
            break
    k += 1
    w, x, y, z = n, 1, 1, 0
    while k:
        if k % 2:
            y, z = w * y + r * x * z, x * y + w * z
        w, x = w * w + r * x * x, 2 * w * x
        w %= p
        x %= p
        y %= p
        z %= p
        k >>= 1
    return y
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
s_t = sum(t)
ans = [0]
for i in range(n):
    ans[-1] = min(ans[-1], v[i])
    for j in range(t[i] * 2):
        ans.append(v[i])
ans.pop()
ans.append(0)
for i in range(1, s_t * 2 + 1):
    ans[i] = min(ans[i - 1] + 1 / 2, ans[i])
for i in range(1, s_t * 2 + 1)[::-1]:
    ans[i - 1] = min(ans[i] + 1 / 2, ans[i - 1])
print(sum(ans) / 2)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from itertools import accumulate

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

Ts = list(accumulate([0] + ts))

# 横向きにカットするイメージ
def solve(begin, end, v):
    # print(' ' * v, begin, end, v, vs[bisect_right(Ts, begin) - 1:bisect_left(Ts, end)])
    if begin >= end:
        return 0
    if begin + 1 == end:
        if v < vs[bisect_right(Ts, begin) - 1]:
            return 0.25
        else:
            return 0
    min_v = min(vs[bisect_right(Ts, begin) - 1:bisect_left(Ts, end)])
    if min_v == v:
        ret = 0
        last = begin
        for i in range(bisect_right(Ts, begin) - 1, bisect_left(Ts, end)):
            if v == vs[i]:
                ret += solve(last, Ts[i], v)
                last = Ts[i + 1]
        ret += solve(last, end, v)
        return ret
    else:
        return end - begin - 1 + solve(begin + 1, end - 1, v + 1)

print(solve(0, Ts[-1], 0))

Submission status: Accepted

Solution code:
from collections import deque

def main():
    with open(0) as f:
        N, *Temp = map(int, f.read().split())
        T, V = Temp[:N], Temp[N:]
        del Temp
    #v-tグラフを仮定して、各区間の境界条件を求める
    v_left = deque([0]) #初期時刻から走査した結果
    v_right = deque([0]) #終了時刻から走査した結果
    #区間i(1<=i<=N)の境界条件は [min(vin[i-1], vout[i-1]), max(vin[i], vout[i])
    #走査処理
    now = 0
    for t,v in zip(T, V):
        now = min(now+t, v)
        v_left.append(now)
    now = 0
    for t, v in zip(reversed(T), reversed(V)):
        now = min(now+t, v)
        v_right.appendleft(now)

    BC = [min(x,y) for x,y in zip(v_left, v_right)] #境界条件
    #区間ごとに2倍の面積計算
    S = [squareMeasure(vin, vout, vsup, t) for vin, vout, vsup, t in zip(BC[:N], BC[1:], V, T)]
    ans = sum(S)/2
    print(ans)

def squareMeasure(vin, vout, vsup, t):
    vmax = (t+vout+vin)/2 #y=x+vinとy=-x+t+vout の交点のy
    if vmax > vsup:
        a, b = vsup-vin, t+vout-vsup #y=vsupと2直線の交点
        S = (vin+vsup)*a + 2*(b-a)*vsup + (vsup+vout)*(t-b)
    else:
        S = (vin+vmax)*(vmax-vin) + (vmax+vout)*(t+vin-vmax)
    return S #2倍の面積である

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# forward
now = 0
for i in range(n):
    if now + t[i] < v[i]:
        v[i] = now + t[i]

    if v[i] <= v[i+1]:
        now = v[i]
    elif t[i] + v[i+1] + now < 2 * v[i]:
        v[i] = (t[i] + v[i+1] + now) / 2
        now = v[i+1]
    else:
        now = v[i+1]

# back
now = 0
for i in range(n-1, -1, -1):
    if now + t[i] < v[i]:
        v[i] = now + t[i]

    if v[i] <= v[i-1]:
        now = v[i]
    elif t[i] + v[i-1] + now < 2 * v[i]:
        v[i] = (t[i] + v[i-1] + now) / 2
        now = v[i-1]
    else:
        now = v[i-1]

ans = 0
now = 0
for i in range(n):
    t1 = v[i] - now
    t3 = v[i] - v[i+1]
    # t2 = t[i] - t1 - t3

    ans += now * t1 + t1 * t1 / 2
    now = v[i] # now += t1

    ans += now * (t[i] - t1 - t3) # ans += now * t2
    # now = now

    ans += now * t3 - t3 * t3 / 2
    now -= t3

print(ans)

Submission status: Accepted

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

# forward
now = 0
for i in range(n):
    if now + t[i] < v[i]:
        v[i] = now + t[i]

    if v[i] <= v[i+1]:
        now = v[i]
    elif t[i] + v[i+1] + now < 2 * v[i]:
        v[i] = (t[i] + v[i+1] + now) / 2
        now = v[i+1]
    else:
        now = v[i+1]

# back
now = 0
for i in range(n-1, -1, -1):
    if now + t[i] < v[i]:
        v[i] = now + t[i]

    if v[i] <= v[i-1]:
        now = v[i]
    elif t[i] + v[i-1] + now < 2 * v[i]:
        v[i] = (t[i] + v[i-1] + now) / 2
        now = v[i-1]
    else:
        now = v[i-1]

ans = 0
now = 0
for i in range(n):
    t1 = v[i] - now
    t3 = v[i] - v[i+1]
    t2 = t[i] - t1 - t3
    ans += now * t1 + t1 * t1 / 2
    now = v[i] # now += t1
    ans += now * t2
    # now = now
    ans += now * t3 - t3 * t3 / 2
    now -= t3

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


# 配列から累積和を返す
def make_cumulative(A):
    C = [0] * (len(A) + 1)
    for i, a in enumerate(A):
        i += 1
        C[i] = C[i - 1] + a
    return C


def main():
    N = NI()
    T = [0] + NLI()
    V = [0] + NLI() + [0]
    B = [[] for _ in range(N+1)]
    cum_T = make_cumulative(T)[1:]

    limits = [[] for _ in range(N)]
    for i, v in enumerate(V):
        for t in range(N):
            if t == i-1:
                limits[t].append([v, 0])
            elif t == i:
                limits[t].append([v, 1])
            elif t < i-1:
                limits[t].append([v + (cum_T[i-1] - cum_T[t]), -1])
            else:
                limits[t].append([v + (cum_T[t] - cum_T[i]), 1])
    limits = [sorted(l) for l in limits]


    ans = 0
    for li, limit in enumerate(limits):
        if limit[0][1] == -1:
            ans += limit[0][0] * T[li+1] - T[li+1]**2 / 2
            continue

        if limit[0][1] == 0:
            next_l = limit[1]
            for j in range(1, len(limit)):
                if limit[j][1] == -1:
                    next_l = limit[j]
                    break
            if next_l[1] == -1 and next_l[0] < limit[0][0] + T[li+1]:
                ans += limit[0][0] * T[li+1] - (limit[0][0]-next_l[0]+T[li+1])**2 / 2
            else:
                ans += limit[0][0] * T[li+1]
            continue

        stay = [l for l in limit if l[1] == 0]
        down = [l for l in limit if l[1] == -1]
        if down == []:
            down_l = [10**5, -1]
        else:
            down_l = down[0]
        if stay == []:
            stay_l = [10**5, 0]
        else:
            stay_l = stay[0]

        if down_l[0] >= limit[0][0] + T[li+1]*2:
            ans += limit[0][0] * T[li + 1] + T[li + 1] ** 2 / 2
            if limit[0][0] < stay_l[0] < limit[0][0] + T[li+1]:
                ans -= (limit[0][0] + T[li+1] - stay_l[0])**2 / 2
        else:
            h = (down_l[0] - limit[0][0])/2
            if stay_l[0] >= limit[0][0] + h:
                ans += (limit[0][0]+h) * T[li+1] - h**2/2 - (T[li+1]-h)**2/2
                continue

            m, M = min(limit[0][0], down_l[0]-T[li+1]), max(limit[0][0], down_l[0]-T[li+1])
            if M < stay_l[0] < limit[0][0] + h:
                ans += (limit[0][0] + h) * T[li + 1] - h ** 2/2 - (T[li + 1] - h) ** 2/2
                ans -= (limit[0][0] + h - stay_l[0]) ** 2
                continue

            if stay_l[0] <= M:
                ans += stay_l[0] * T[li+1] - (stay_l[0]-limit[0][0])**2 / 2
                continue

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)
ans = [0]

for i in range(N):
  ans[-1] = min(ans[-1],v[i])
  for j in range(t[i]*2):
    ans.append(v[i])

ans[-1] = 0

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

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

print(sum(ans)/2)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
t = LI()
v = LI()

max_v = [0]*(N+1)  # 0秒後,t1秒後,t1+t2秒後,…の時点で出せる最大速度
for i in range(N-1):
    max_v[i+1] = min(v[i],v[i+1],max_v[i]+t[i])
for i in range(N-2,-1,-1):
    max_v[i+1] = min(max_v[i+1],v[i],v[i+1],max_v[i+2]+t[i+1])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    
    
    length = sum(t)*2
    
    dp = [0]*(length+1)
    border = v[0]
    count = t[0]*2
    index = 0
    for i in range(length):
        dp[i+1] = min(dp[i]+0.5, border)
        count -= 1
        if i == length-1:
            break
        if count == 0:
            index += 1
            border = v[index]
            count = t[index]*2
    
    dp[length] = 0
    border = v[n-1]
    count = t[n-1]*2
    index = n-1
    for i in range(length, 0, -1):
        dp[i-1] = min([dp[i]+0.5, border, dp[i-1]])
        count -= 1
        if i == 0:
            break
        if count == 0:
            index -= 1
            border = v[index]
            count = t[index]*2
    
    ans = 0
    for i in range(length):
        ans += (dp[i]+dp[i+1])/4
        
    print(ans)
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
t = list(map(lambda x: int(x)*2, input().split()))
v = list(map(int, input().split()))
s = [None]*n
tmp = 0
for i in range(n):
    tmp += t[i]
    s[i] = tmp
s.insert(0,0)
l1 = [] # (時刻, 速度)
l2 = [(0,0)] # (時刻, 速度)
for i in range(n):
    l1.append((s[i],v[i]))
    l2.append((s[i+1],v[i]))
l1.append((s[-1],0))
vs = [0]*s[-1]
ind = 0
ind1 = 0
ind2= 0
prv = 0
for i in range(s[-1]):
    while ind+1<len(s) and i>=s[ind+1]:
        ind += 1
    while ind1+1<len(l1) and i>=l1[ind1+1][0]:
        ind1 += 1
    while ind2+1<len(l2) and i>=l2[ind2+1][0]:
        ind2 += 1
#     print(i, ind, ind1, ind2)
    vs[i] = min(prv+1, v[ind], min((l1[j][1]+(l1[j][0]-i)*0.5) for j in range(ind1+1,len(l1))),
                   min((l2[j][1]+(i-l2[j][0])*0.5) for j in range(ind2+1)))
    prv = vs[i]
vs.append(0)
ans = 0
for i in range(len(vs)-1):
    ans += (vs[i]+vs[i+1])/2
print(ans/2)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    t = [int(i) for i in ipt().split()]
    v = [int(i) for i in ipt().split()]
    tsm = sum(t)
    st = [0]
    for i in t:
        st.append(st[-1]+i)
    sp = [min(i/2,tsm-i/2) for i in range(tsm*2+1)]

    for i,ti in enumerate(t):
        vi = v[i]
        t0 = st[i]*2
        sf = False
        ff = False
        if sp[t0] > vi:
            sf = True
        if sp[t0+ti*2] > vi:
            ff = True
        for j in range(ti*2+1):
            if sp[t0+j] > vi:
                sp[t0+j] = vi
        if sf:
            for j in range(1,1000000):
                if sp[t0-j] > vi+j/2:
                    sp[t0-j] = vi+j/2
                else:
                    break
        t0 += ti*2
        if ff:
            for j in range(1,1000000):
                if sp[t0+j] > vi+j/2:
                    sp[t0+j] = vi+j/2
                else:
                    break
#        print(sp)

    print(sum(sp)/2)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def get_current_v_max(t, t_from, t_to, v_max):
    # 制約(t_from, t_to, v_max)の元で、時刻tにおける最大速度を返す
    if t <= t_from:
        return - t + t_from + v_max
    elif t_to <= t:
        return t - t_to + v_max
    else:
        return v_max


def main():
    N = int(input())
    # t, vを縦横2倍にスケールしておけば、グラフの交点が全部格子点上に乗る
    # 最後にt-vグラフの面積を1/4倍する
    SCALE = 2
    T = list(map(lambda t: int(t) * SCALE, input().split()))
    V = list(map(lambda v: int(v) * SCALE, input().split()))
    MAX_V = 100 * SCALE
    # (t_from, t_to, v_max): t_from～t_toの間は速度v_max以下
    constraint_list = [(0, 0, 0)]
    t_from = 0
    for t, v in zip(T, V):
        constraint_list.append((t_from, t_from + t, v))
        t_from += t
    constraint_list.append((t_from, t_from, 0))
    # 各時刻においてすべての制約を満たす最大速度を求めていく
    v_max_list = [MAX_V] * (sum(T) + 1)
    for t in range(sum(T) + 1):
        for t_from, t_to, v_max in constraint_list:
            v_max_list[t] = min(v_max_list[t], get_current_v_max(t, t_from, t_to, v_max))
    # 答えは走行距離なので、t-vグラフの面積を求める
    ans = 0
    for t in range(sum(T)):
        ans += (v_max_list[t] + v_max_list[t + 1]) / 2
    print(ans / (SCALE**2))


if __name__ == '__main__':
    main()

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)