Problem:


﻿Score : 400 points

Problem Statement

In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express.

In the plan developed by the president Takahashi, the trains will run as follows:

A train will run for (t_1 + t_2 + t_3 + ... + t_N) seconds.

In the first t_1 seconds, a train must run at a speed of at most v_1 m/s (meters per second). Similarly, in the subsequent t_2 seconds, a train must run at a speed of at most v_2 m/s, and so on.

According to the specifications of the trains, the acceleration of a train must be always within ±1m/s^2. Additionally, a train must stop at the beginning and the end of the run.

Find the maximum possible distance that a train can cover in the run.

Constraints

1 \leq N \leq 100

1 \leq t_i \leq 200

1 \leq v_i \leq 100

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
t_1 t_2 t_3 … t_N
v_1 v_2 v_3 … v_N

Output

Print the maximum possible that a train can cover in the run.

Output is considered correct if its absolute difference from the judge's output is at most 10^{-3}.

Sample Input 1

1
100
30

Sample Output 1

2100.000000000000000

The maximum distance is achieved when a train runs as follows:

In the first 30 seconds, it accelerates at a rate of 1m/s^2, covering 450 meters.

In the subsequent 40 seconds, it maintains the velocity of 30m/s, covering 1200 meters.

In the last 30 seconds, it decelerates at the acceleration of -1m/s^2, covering 450 meters.

The total distance covered is 450 + 1200 + 450 = 2100 meters.

Sample Input 2

2
60 50
34 38

Sample Output 2

2632.000000000000000

The maximum distance is achieved when a train runs as follows:

In the first 34 seconds, it accelerates at a rate of 1m/s^2, covering 578 meters.

In the subsequent 26 seconds, it maintains the velocity of 34m/s, covering 884 meters.

In the subsequent 4 seconds, it accelerates at a rate of 1m/s^2, covering 144 meters.

In the subsequent 8 seconds, it maintains the velocity of 38m/s, covering 304 meters.

In the last 38 seconds, it decelerates at the acceleration of -1m/s^2, covering 722 meters.

The total distance covered is 578 + 884 + 144 + 304 + 722 = 2632 meters.

Sample Input 3

3
12 14 2
6 2 7

Sample Output 3

76.000000000000000

The maximum distance is achieved when a train runs as follows:

In the first 6 seconds, it accelerates at a rate of 1m/s^2, covering 18 meters.

In the subsequent 2 seconds, it maintains the velocity of 6m/s, covering 12 meters.

In the subsequent 4 seconds, it decelerates at the acceleration of -1m/s^2, covering 16 meters.

In the subsequent 14 seconds, it maintains the velocity of 2m/s, covering 28 meters.

In the last 2 seconds, it decelerates at the acceleration of -1m/s^2, covering 2 meters.

The total distance covered is 18 + 12 + 16 + 28 + 2 = 76 meters.

Sample Input 4

1
9
10

Sample Output 4

20.250000000000000000

The maximum distance is achieved when a train runs as follows:

In the first 4.5 seconds, it accelerates at a rate of 1m/s^2, covering 10.125 meters.

In the last 4.5 seconds, it decelerates at the acceleration of -1m/s^2, covering 10.125 meters.

The total distance covered is 10.125 + 10.125 = 20.25 meters.

Sample Input 5

10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70

Sample Output 5

20291.000000000000



Sample input:
1
100
30


Sample output:
2100.000000000000000

Submission status: Accepted

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

for i in range(n):
    t[i] *= 2.0
    v[i] *= 2.0

v.append(0.0)

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

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

ans = 0.0
speed = 0.0
k = 0
st = int(t[n - 1] + 0.1)

for i in range(st):
    if i >= t[k]:
        k += 1
    
    ans += speed

    limit = min(v[k], v[k + 1] + t[k] - i - 1)
    if speed < limit:
        ans += 0.5
        speed += 1.0
    elif speed > limit:
        ans -= 0.5
        speed -= 1.0

ans /= 4.0

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
*t, = map(int, input().split())
*v, = map(int, input().split())
sumt = sum(t)

sv = [0]
for i in range(N):
    for j in range(t[i]*2):
        sv.append(v[i])
sv.append(0)

# dp[i][j] := i/2秒後に速度がj/2のときの最大距離
dp = [[-float('inf')]*201 for _ in range(sumt*2+1)]
dp[0][0] = 0
for i in range(1, len(dp)):
    maxj = min(sv[i], sv[i+1])*2
    for j in range(len(dp[i])):
        k = 0.25*j
        # 変化なし
        if j <= maxj:
            dp[i][j] = max(dp[i][j], dp[i-1][j]+k)
        # 加速
        if (j+1) <= maxj:
            dp[i][j+1] = max(dp[i][j+1], dp[i-1][j]+k+0.25)
        # 減速
        if j > 0 and (j-1) <= maxj:
            dp[i][j-1] = max(dp[i][j-1], dp[i-1][j]+k-0.25)

print(dp[-1][0])

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop
from bisect import bisect_left, bisect_right, insort_left
read=sys.stdin.read
readline=sys.stdin.readline

def main():
    n=int(readline())
    t,v=(list(map(int,l.split())) for l in read().splitlines())
    vi=[(x,i+1) for i,x in enumerate(v)]
    x=[0]*(n+2)
    y=[0]*(n+1)
    x[0]=0
    y[0]=0
    y[-1]=0
    for i in range(1,n+1):
        x[i]=x[i-1]+t[i-1]
    x[n+1]=x[n]
    heapify(vi)
    ans=0
    v=[0]+v+[0]
    memo=[0,n+1]
    while vi:
        e=heappop(vi)
        insort_left(memo,e[1])
        idx=bisect_left(memo,e[1])
        _i=memo[idx-1]
        i_=memo[idx+1]
        i=memo[idx]
        sx=x[_i]
        gx=x[i_-1]
        sy=y[_i]
        gy=y[i_-1]
        h=e[0]
        y[i]=min(h,gx-x[i]+gy,x[i]-sx+sy)
        y[i-1]=min(h,gx-x[i-1]+gy,x[i-1]-sx+sy)
        dw=gx-sx
        dh=abs(gy-sy)
        be=max(0,dw-(2*max(v[_i],v[i_])-sy-gy))
        ht=min(h-v[_i],h-v[i_],be/2)
        te=max(0,be-2*ht)
        ans+=(te+be)*ht/2
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
ADJ = 10**2
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 sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

def descrease_dist(dv, dt):
    return dv * (dt - dv / 2) + dv * dv / 4


def main():
    N = int(input())
    T = list(map(int, input().split()))
    T = list(accumulate(T))
    V = list(map(int, input().split()))
    """
    ヒストグラムに対して傾き１の山を内包させる問題だと捉える。
    まず山の凸凹は0.5秒おきに変化するので、各点でのvの値を観察する。
    そして次がポイントだが、各vの値は
        V[t] = min(V[t - 0.5] + 0.5, V[t])
    に更新することでヒストグラムに対して値が増える側が傾き１の斜め線になり、
    さらに
        V[t] = min(V[t + 0.5], V[t])
    の更新をかけると値が減る側も傾き１の斜め線にな利、これが答え。

    「右側と左側からそれぞれ更新」が肝でした。
    """
    velocity = [100] * (T[-1] * 2 + 1)
    velocity[0] = 0
    velocity[-1] = 0
    pre_t = 0
    for i, t in enumerate(T):
        for j in range(pre_t * 2, t * 2 + 1):
            velocity[j] = min(V[i], velocity[j])
        pre_t = t

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


    dist = 0
    pre_v = 0
    for t in range(1, T[-1] * 2 + 1):
        dist += (velocity[t] + velocity[t - 1])
    print(dist / 4)

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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret

N = I()
T = IL()
V = IL()
ACCT = ACC1(T)

TALL = sum(T)

Lspeed = [min(i/2,TALL-i/2) for i in range(TALL*2+1)]

def f(i,j):
  t = i/2
  start = ACCT[j]
  end = ACCT[j+1]
  if start<=t<=end:
    return V[j]
  elif t<start:
    return V[j]+(start-t)
  else:
    return V[j]+(t-end)

for i in range(TALL*2+1):
  Lspeed[i] = min(Lspeed[i],min(f(i,j) for j in range(N)))

ans = 0
for i in range(TALL*2):
  ans += Lspeed[i]+Lspeed[i+1]

print(ans/4)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret

N = I()
T = IL()
V = IL()
ACCT = ACC1(T)

TALL = sum(T)

Lspeed = [None for i in range(TALL*2+1)]
Lspeed[0] = 0

for i in range(N):
  start_time = ACCT[i]
  vmax = V[i]
  if i != N-1:
    next_vmax = V[i+1]
  else:
    next_vmax = INF
  for j in range(1,T[i]*2+1):
    Lspeed[start_time*2+j] = min(Lspeed[start_time*2]+j/2,next_vmax+T[i]-j/2,vmax)

Rspeed = [None for i in range(TALL*2+1)]
Rspeed[0] = 0
Tinv = T[::-1]
Vinv = V[::-1]
ACCTinv = ACC1(Tinv)
for i in range(N):
  start_time = ACCTinv[i]
  vmax = Vinv[i]
  if i != N-1:
    next_vmax = Vinv[i+1]
  else:
    next_vmax = INF
  for j in range(Tinv[i]*2+1):
    Rspeed[start_time*2+j] = min(Rspeed[start_time*2]+j/2,next_vmax+Tinv[i]-j/2,vmax)
    
    
Fspeed = [min(Lspeed[i],Rspeed[TALL*2-i]) for i in range(TALL*2+1)]

ans = 0
for i in range(TALL*2):
  ans += Fspeed[i]+Fspeed[i+1]
print(ans/4)

Submission status: Accepted

Solution code:
N=int(input())
T=[1]+list(map(int,input().split()))+[1]
V=[0]+list(map(int,input().split()))+[0]
T=list(map(lambda x:x*2,T))
V=list(map(lambda x:x*2,V))
X=[i for i in range(sum(T)+1)]
C=[0]
X[-1]=0
for i in range(len(T)):
  C.append(C[i]+T[i])
for i in range(N+2):
  for j in range(C[i+1]):
    if j>=C[i]:
      X[j]=min(X[j],V[i])
    else:
      X[j]=min(X[j],V[i]+C[i]-j-1)
for i in range(len(X)-1):
  X[i+1]=min(X[i+1],X[i]+1)
print(sum(X)/4)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    back_lim = []
    lim = []
    for i in range(n):
        for _ in range(t[i]):
            back_lim.append(v[i])
            lim.append(v[i])
    back_lim.append(0)
    for i in reversed(range(len(back_lim)-1)):
        back_lim[i] = min(back_lim[i], back_lim[i+1]+1)
    ans = 0.0
    p = 0
    for i in range(len(back_lim)-1):
        if p < back_lim[i+1]:
            if p < lim[i]:
                ans += p + 0.5
                p += 1
            else:
                ans += p
        elif p == back_lim[i+1]:
            if p < lim[i]:
                ans += p + 0.25
            else:
                ans += p
        else:
            ans += p - 0.5
            p -= 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline
N = int(input())
T = [0] + list(map(int,input().split()))
V = list(map(int,input().split()))
T = [2*t for t in T]
V = [2*v for v in V]

cT = list(accumulate(T))

fs = [lambda x : x, lambda x : -x + cT[-1]]
for i in range(N):
    fs.append(lambda x, i = i: max(V[i], -x+cT[i] + V[i], x-cT[i+1] + V[i]))

last = cT[-1]

vs = []
for x in range(last+1):
    temp = 10**10
    for f in fs:
        temp = min(temp,f(x))
    vs.append(temp)

ans = (sum(vs) + sum(vs[1:-1]))/8
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate
    dh = 10

    n = int(readline())
    t_ = [0] + list(map(int, readline().split()))
    t_list = list(accumulate(t_))
    v_list = list(map(int, readline().split())) + [0]
    lim = [0] * (sum(t_list) * dh + 1)

    for i in range(n):
        st = dh * t_list[i]
        nt = dh * t_list[i + 1]
        cv = v_list[i]
        pv = lim[st]
        nv = v_list[i + 1]
        for ct in range(st, nt + 1):
            lim[ct] = min(cv, pv + (ct - st) / dh)

    for i in range(1, n + 1):
        st = dh * t_list[i]
        sv = v_list[i]
        for ct in range(st, -1, -1):
            lim[ct] = min(lim[ct], sv + (st - ct) / dh)

    ans = 0
    pv = 0
    for v in lim[1:]:
        ans += (pv + (v - pv) / 2) / dh
        pv = v

    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()))
max_t = sum(T)
vl = [0]*(max_t+1)
vr = [0]*(max_t+1)
vm = [0]*(max_t+1)
t = 0
for s, u in zip(T,V):
  for i in range(t,t+s):
    vm[t] = u
    t += 1
t = 1
for s, u in zip(T,V):
  for i in range(t, t+s):
    vl[t] = min(u, vl[t-1]+1)
    t += 1
t = max_t
for s, u in zip(T[::-1],V[::-1]):
  for i in range(t-s,t)[::-1]:
    vr[t-1] = min(u,vr[t]+1)
    t -= 1
v = [min(vl[i],vr[i]) for i in range(max_t+1)]
#print(vm)
#print(vl)
#print(vr)
#print(v)
ans = 0
for i in range(max_t):
  ans += (v[i] + v[i+1]) / 2
  if v[i] == v[i+1] and v[i] != vm[i]:
    ans += 0.25
print("{:.10f}".format(ans))

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v.append(0)
t.append(1)
sumoftimes=[0]
currentsum=0
for i in range(n+1):
  currentsum+=t[i]
  sumoftimes.append(currentsum)
ans=[]
for i in range(2*sumoftimes[n]+1):
  a=10**9
  for j in range(n+1):
    if 2*sumoftimes[j]<=i:
      if j>0:
        a=min(a,(i/2-sumoftimes[j]+v[j-1]))
    else:
      a=min(a,(sumoftimes[j]-i/2+v[j]))
  a=min(a,i/2)
  for j in range(n):
    if i<2*sumoftimes[j+1]:
      a=min(a,v[j])
      break
  if i==2*sumoftimes[n]:
    a=0
  ans.append(a)
finalans=0
for i in range(len(ans)-1):
  finalans+=(ans[i]+ans[i+1])/4
print(finalans)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
T=sum(t)
ansv=[0]
for i in range(n):
  ansv[-1]=min(ansv[-1],v[i])
  for j in range(t[i]*2):
    ansv.append(v[i])
ansv[-1]=0
#for i in range(len(ansv)):
#  print(i/2,ansv[i])
for i in range(2*T):
  ansv[i+1]=min(ansv[i]+0.5,ansv[i+1])
for i in range(2*T,0,-1):
  ansv[i-1]=min(ansv[i]+0.5,ansv[i-1])
print(sum(ansv)/2)
#print(len(ansv))
#for i in range(len(ansv)):
#  print(i/2,ansv[i])

Submission status: Accepted

Solution code:
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):
    s = left[i-1]
    left[i] = min(s+t[i],v[i],v[i+1])
for i in range(n-1,0,-1):
    s = right[i+1]
    right[i] = min(s+t[i+1],v[i],v[i+1])

ad = [min(x,y) for x,y in zip(left,right)]

def cal(le,ri,t,v):
    x = v-le+v-ri
    if x >= t:
        v = (le+ri+t)/2
        x = t
    d = (le+v)*(v-le)/2
    d += v*(t-x)
    d += (ri+v)*(v-ri)/2
    return d

ans = 0
for i in range(1,n+1):
    ans += cal(ad[i-1],ad[i],t[i],v[i])
print(ans)

Submission status: Accepted

Solution code:
# Atcoder Express
from bisect import bisect_left, bisect_right
N = int(input())
time = list(map(int, input().split()))
vel = list(map(int, input().split()))
sum_t = [0 for i in range(N+1)]

for i in range(1, N+1):
    sum_t[i] = sum_t[i-1]+time[i-1]

dp = [[-float("inf") for j in range(101)] for i in range(20001)]
# dp[t][v]=開始からt秒後に速度v で走っている時に、t秒後に実現できる最大の移動距離
dp[0][0] = 0

for i in range(1, sum_t[-1]+1):
    # i秒後における更新

    bef = bisect_left(sum_t, i-1)
    phase = bisect_left(sum_t, i)

    bef_bound = vel[bef-1]  # i-1秒時点における速度制限
    bound = vel[phase-1]    # i秒後における速度制限
    if bef == 0:
        bef_bound = 100
        
    if bef_bound < bound:
        for j in range(bef_bound+2):
            if j == 0:
                if j+1 <= bef_bound:
                    dp[i][j] = max(dp[i-1][j]+j+0.25, dp[i-1][j+1]+j+0.5)
                else:
                    if j == bef_bound:
                        dp[i][j] = dp[i-1][j]+j+0.25

            elif j >= 1:
                if j+1 <= bef_bound:
                    dp[i][j] = max(dp[i-1][j-1]+j-0.5, dp[i-1]
                                   [j]+j+0.25, dp[i-1][j+1]+j+0.5)
                else:
                    if j == bef_bound:
                        dp[i][j] = max(dp[i-1][j-1]+j-0.5, dp[i-1][j]+j+0.25)
                    else:
                        if j-1 == bef_bound:
                            dp[i][j] = dp[i-1][j-1]+j-0.5

    elif bef_bound >= bound:
        for j in range(bound):
            if j == 0:
                # j+1<=bef_bound:
                dp[i][j] = max(dp[i-1][j]+j+0.25, dp[i-1][j+1]+j+0.5)
            elif j >= 1:
                dp[i][j] = max(dp[i-1][j-1]+j-0.5, dp[i-1]
                               [j]+j+0.25, dp[i-1][j+1]+j+0.5)

        dp[i][bound] = max(dp[i-1][bound]+bound, dp[i-1][bound-1]+bound-0.5)


ans = dp[sum_t[-1]][0]
print(ans)

Submission status: Accepted

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

maxv = [0] + [min(v[i], v[i+1]) for i in range(N-1)] + [0]
for i in reversed(range(N)):
  if maxv[i] - maxv[i+1] > t[i]:
    maxv[i] = maxv[i+1] + t[i]
for i in range(N):
  if maxv[i+1] - maxv[i] > t[i]:
    maxv[i+1] = maxv[i] + t[i]

def kyori(start, stop, mxv, ti):
  if stop >= start:
    if stop - start >= ti:
      return (stop+start)*ti /2
    elif mxv <= stop:
      return ti*mxv - (mxv-start)**2 /2
    else:
      x = (stop-start+ti)/2
      if mxv >= start + x:
        return (start+start+x)*x /2 + (stop+stop+ti-x)*(ti-x) /2
      else:
        return ti*mxv - ((mxv-start)**2 + (mxv-stop)**2)/2
  else:
    x = (stop-start+ti)/2
    if mxv >= start + x:
      return (start+start+x)*x /2 + (stop+stop+ti-x)*(ti-x) /2
    else:
      return ti*mxv - ((mxv-start)**2 + (mxv-stop)**2)/2


ans = 0
for i in range(N):
  ans += kyori(maxv[i], maxv[i+1], v[i], t[i])

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    ts = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    vs=tuple(map(int, input().split()))

    vmax=max(vs)
    tmax=sum(ts)
    inf=-vmax*tmax

    dp=[[inf]*(vmax+1) for _ in range(tmax+1)]
    dp[0][0]=0
    ti=0
    tcount=0
    for t in range (1,tmax+1):
        tcount+=1
        if tcount>ts[ti]:
            tcount-=ts[ti]
            ti+=1
        #print(tcount,ti,tmax)
        cvmax=vs[ti]
        for v in range(0,vmax+1):
            if v >cvmax:
                dp[t][v]=inf
                continue
            dp[t][v]=dp[t-1][v]+v
            if v+0.5<cvmax:
                dp[t][v]=max(dp[t][v],dp[t-1][v]+v+0.25)
            if v+1<=cvmax:
                dp[t][v]=max(dp[t][v],dp[t-1][v+1]+(2*v+1)*0.5)
            if v-1>=0:
                dp[t][v]=max(dp[t][v],dp[t-1][v-1]+(2*v-1)*0.5)
    print(dp[tmax][0])
    #print(dp)



        


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
u = [0]
for vi, ti in zip(v, t):
  u[-1] = min(u[-1], vi)
  u += [vi] * (ti * 2)

u[-1] = 0
U = u.copy()
T = len(u)
for i in range(1, T):
  u[i] = min(u[i], u[i-1]+0.5)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    t = LI()
    v = LI() + [0]
    p = [0] * (N+1)

    for i in range(N):
        p[i+1] = min(p[i]+t[i],v[i],v[i+1])
        j = i
        while p[j] > p[j+1] + t[j] and j > 0:
            p[j] = p[j+1]+t[j]
            j -= 1
    ans = 0
    for i in range(N):
        s1 = v[i] - p[i]
        s2 = v[i] - p[i+1]
        ans += v[i] * t[i] - s1 * s1 / 2 - s2 * s2 / 2
        if s1 + s2 > t[i]:
            ans += (s1 + s2 - t[i]) ** 2 / 4
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    t = LI()
    v = LI() + [0]
    p = [0] * (N+1)

    for i in range(N):
        p[i+1] = min(p[i]+t[i],v[i],v[i+1])
        j = i
        while p[j] > p[j+1] + t[j] and j > 0:
            p[j] = min(v[j],p[j+1]+t[j])
            j -= 1
    ans = 0
    for i in range(N):
        s1 = v[i] - p[i]
        s2 = v[i] - p[i+1]
        ans += v[i] * t[i] - s1 * s1 / 2 - s2 * s2 / 2
        if s1 + s2 > t[i]:
            ans += (s1 + s2 - t[i]) ** 2 / 4
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

def calc_area(v1,v2,t,lim):
    if v1 > v2:
        v1,v2 = v2,v1
    if v2 == lim:
        if lim - v1 < t:
            return t*lim - (lim - v1)*(lim - v1)/2
        else:
            return (v1 + v2)*t/2
    else:
        if 2*lim - v1 - v2 < t:
            return t*lim - (lim - v1)*(lim - v1)/2 - (lim - v2)*(lim - v2)/2
        else:
            mid = (t + v2 - v1)/2
            return (mid + 2*v1)*mid/2 + (t - mid + 2*v2)*(t - mid)/2

def calc(N,T,V,maxv):
    ans = 0
    v = 0
    for i in range(N):
        next_v = min(v + T[i],maxv[i])
        ans += calc_area(v,next_v,T[i],V[i])
        v = next_v
    return ans

maxV = [0] * N
for i in range(N - 2,-1,-1):
    maxV[i] = min(maxV[i + 1] + T[i + 1],V[i],V[i + 1])
ans = calc(N,T,V,maxV) 
print(ans)