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:
import heapq
n=int(input())
inf=10000000000000
#始まりと終わりを保持
#同じオブジェクトにするやつで一時間溶かした、しね
ans=[[-1,-1] for i in range(n)]
ans[-1][1]=0
ans[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))
for i in range(n):
    #print(ans)
    y=heapq.heappop(v2)
    #print(y[1])
    #print(ans[y[1]])
    #print(y)
    #始まりをまずは決める
    if ans[y[1]][0]==-1:
        #print(2)
        now1=0
        ansi1=inf
        for j in range(y[1]-1,-1,-1):
            #print(ans1)
            if ans[j][1]!=-1:
                ansi1=min(ansi1,ans[j][1]+now1)
            now1+=t[j]
            if ans[j][0]!=-1:
                ansi1=min(ansi1,ans[j][0]+now1)
        now1=0
        for j in range(y[1],n):
            if ans[j][0]!=-1:
                ansi1=min(ansi1,ans[j][0]+now1)
            now1+=t[j]
            if ans[j][1]!=-1:
                ansi1=min(ansi1,ans[j][1]+now1)  
        ans[y[1]][0]=min(ansi1,y[0])
        ans[y[1]-1][1]=ans[y[1]][0]
        #print(ansi1)
    if ans[y[1]][1]==-1:
        #print(3)
        now2=0
        ansi2=inf
        for j in range(y[1],-1,-1):
            if ans[j][1]!=-1:
                ansi2=min(ansi2,ans[j][1]+now2)
            now2+=t[j]
            if ans[j][0]!=-1:
                ansi2=min(ansi2,ans[j][0]+now2)
        now2=0
        for j in range(y[1]+1,n):
            if ans[j][0]!=-1:
                ansi2=min(ansi2,ans[j][0]+now2)
            now2+=t[j]
            if ans[j][1]!=-1:
                ansi2=min(ansi2,ans[j][1]+now2)  
        ans[y[1]][1]=min(ansi2,y[0])
        ans[y[1]+1][0]=ans[y[1]][1]
        #print(ansi2)
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)
#print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    T=LI()
    V=LI()
    T_sum = sum(T)

    #初期化
    max_V = [inf]*(2*T_sum+1)
    now = 0
    for i,(t,v) in enumerate(zip(T,V)):
        max_V[now] = min(max_V[now], v)
        for dt in range(2*t):
            now += 1
            max_V[now] = min(max_V[now], v)
    max_V[0] = 0
    max_V[-1] = 0


    #前から
    for i in range(2*T_sum):
        max_V[i+1] = min(max_V[i+1], max_V[i]+0.5)

    for i in range(2*T_sum)[::-1]:
        max_V[i] = min(max_V[i], max_V[i+1]+0.5)

    #計算部分
    ans = 0
    for i in range(2*T_sum):
        ans += (max_V[i]+max_V[i+1])/2

    ans /= 2
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
l=[]
for i in range(N):
    l+=[v[i]]*t[i]
l.append(0)
T=sum(t)
for i in range(T-1,0,-1):
    if l[i]<l[i+1]:
        l[i+1]=l[i]+0.5
s=[100]*(T+1)
s[0],s[-1]=0,0
c=1
while c:
    c=0
    for i in range(1,T):
        if s[i]>s[i-1]+1:
            s[i]=s[i-1]+1
            c=1
        if s[i]>s[i+1]+1:
            s[i]=s[i+1]+1
            c=1
        if s[i]>l[i]:
            s[i]=int(l[i])
            c=1
a=0
for i in range(T):
    if s[i+1]!=s[i]:
        a+=(s[i+1]+s[i])/2
    else:
        if s[i]<l[i]:
            a+=s[i]+0.25
        else:
            a+=s[i]
print(a)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
t.append(0)
v.append(0)
nowv = 0
ans = 0
for i in range(n):
    m = v[i]
    t0 = 0
    for j in range(i+1,n+1):
        mnow = v[j]
        #print(v[j],i)
        for k in range(j,i,-1):
            if mnow + t[k] <= v[k]:
                mnow += t[k]
            else:
                mnow = v[k]
            #print(mnow)
        m = min(m,mnow)
        t0 += t[j]
    m = min(m,nowv+t[i])
    #print(m)
    if m == v[i]:
        if nowv+t[i] <= v[i]:
            ans += (2*nowv+t[i])*t[i]/2
        else:
            #print(nowv,v[i])
            ans += (nowv+v[i])*(abs(v[i]-nowv))/2 + v[i]*(t[i]-v[i]+nowv)
    else:
        if m <= nowv:
            a = nowv - m
            b = (t[i]-a)/2
            if nowv + b <= v[i]:
                ans += a*(m+nowv)/2
                ans += (2*nowv+b)*b
            else:
                ans += (nowv+v[i])*(v[i]-nowv)/2
                ans += v[i]*(t[i]-(v[i]-nowv)-(v[i]-m))
                ans += (m+v[i])*(v[i]-m)/2
        else:
            a = m - nowv
            b = (t[i]-a)/2
            if nowv + a+ b <= v[i]:
                ans += a*(m+nowv)/2
                ans += (2*m+b)*b
                #print(a,b)
            else:
                ans += (nowv+v[i])*(v[i]-nowv)/2
                ans += v[i]*(t[i]-(v[i]-nowv)-(v[i]-m))
                ans += (m+v[i])*(v[i]-m)/2
    #print(ans)
    nowv = m
    #print(nowv)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ts = list(map(int, input().split())) + [0]
vs = list(map(int, input().split())) + [0]
cst = [0] * (N + 1)
for i in range(N): cst[i + 1] = cst[i] + ts[i]

def check(l, r, ti, x):
  return ((x - l) + max(0, x - r)) <= ti
ps = set()
dp = [0] * (N + 1)
#print(cst)
for i in range(N):
  ok = 0
  ng = vs[i] + 0.1 ** 12
  l = min(dp[i], vs[i])
  r = min(vs[i + 1], cst[-1] - cst[i + 1])
  for j in range(i + 1, N): r = min(r, vs[j] + (cst[j] - cst[i + 1]))
  ti = ts[i]
  while ng - ok > 0.1 ** 12:
    m = (ok + ng) / 2
    if check(l, r, ti, m): ok = m
    else: ng = m
  if (cst[-1] - (abs(ok - l) + cst[i])) <= ok:
    ng = ok + 0
    ok = 0
    while ng - ok > 0.1 ** 12:
      m = (ok + ng) / 2
      if abs(l - m) + m <= cst[-1] - cst[i]: ok = m
      else: ng = m
    ps.add((cst[-1] - ok, ok))
    break
  ps.add((abs(ok - l) + cst[i], ok))
  ps.add((cst[i + 1] - max(0, ok - r), ok))
  #print(ok, ng, l, r, cst[i + 1])
  dp[i + 1] = min(ok, r)

ps.add((0, 0))
ps.add((cst[-1], 0))
#print(ps)
sps = sorted(ps, key = lambda x: x[0])
res = 0
for i in range(len(sps)):
  res += sps[i][0] * sps[i - 1][1] - sps[i][1] * sps[i - 1][0]
print(abs(res) / 2)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

def should_sd(cur_t, cur_v, next_ix, T, V):
    for i in range(next_ix, len(T)):
        Vsup = V[i+1]
        rem_t = T[i] - cur_t
        if cur_v - Vsup >= rem_t:
            return True
    return False

def main():
    N = I()
    T = LI()
    V = LI()
    V.append(0)
    for i in range(N-1):
        T[i+1] += T[i]
    cur_t = 0
    cur_v = 0
    prev_v = 0
    ix = 0
    next_ix = 0
    area = 0
    while cur_t < T[-1]:
        if cur_t == T[next_ix]:
            next_ix += 1
        if should_sd(cur_t, cur_v, next_ix, T, V):
            prev_v = cur_v
            cur_v -= 0.5
        else:
            if cur_v < V[next_ix]:
                prev_v = cur_v
                cur_v += 0.5
            else:
                prev_v = cur_v
        # add menseki
        p = (prev_v + cur_v) * 0.5 / 2
        area += p
        cur_t += 0.5
    print(area)
main()

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N=I()
    t=LI()
    v=LI()
    T=sum(t)*2+1#0.5秒刻み
    
    for i in range(N-1):
        t[i+1]+=t[i]
    t.append(0)#-1用
        
    vt=[1000]*T    
        
    #[l,r]の区間(秒)で上限がmvという条件の時，各時間での速度上限
    def set_v(l,r,mv):
        ll=2*l
        rr=2*r
        for i in range(T):
            if ll<=i and i<=rr:
                vt[i]=min(vt[i],mv)
            else:
                x=min(abs(i-ll),abs(i-rr))
                vv=mv+x/2
                vt[i]=min(vt[i],vv)
                
    for i in range(N):
        set_v(t[i-1],t[i],v[i])
    
    #両端
    set_v(0,0,0)
    set_v((T-1)//2,(T-1)//2,0)    
    
        
    ans=0
    for i in range(T-1):
        ans+=(vt[i]+vt[i+1])/4
        
    print(ans)
        

        
    
    
main()


"""

#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    t=LI()
    mv=LI()
    mv.append(0)
    
    
    
    #v0で始まってv1でおわる,最高vmまで出して良い,t廟の区間
    def calc(v0,v1,vm,t):
        vv = (t-abs(v1-v0))/2+max(v0,v1) #vmを気にしなければどこまで上がれるか
        
        if abs(v1-v0)==t:
            return (v0+v1)*t/2
        elif v1==vm or v0==vm:
            return (v1+v0)*abs(v1-v0)/2 +max(v1,v0)*(t-abs((v1-v0)))
        elif vv<vm:
            return (vv+v0)*(vv-v0)/2 + (vv+v1)*(vv-v1)/2
        else:
            return (v0+vm)*(vm-v0)/2 + vm*(t-(vm-v0)-(vm-v1)) + (vm+v1)*(vm-v1)/2 
         
         
    #区間端での速度,手前から決めていき，無理が生じたら手前を下げていく(Nが小さいので)
    v=[1000]*(N+1)
    v[0]=0
    v[-1]=0
    
    for i in range(N):
        v[i+1]=min(v[i]+t[i],mv[i],mv[i+1])
        if v[i]-v[i+1]>t[i]:#下げきれないなら
            j=i
            while v[j]-v[j+1]>t[j]:
                v[j]=v[j+1]+t[j]
                j-=1
                
                
    ans=0
    for i in range(N):
        ans+=calc(v[i],v[i+1],mv[i],t[i])
    print(ans)
 

main()


"""

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    t=LI()
    mv=LI()
    mv.append(0)
    
    
    
    #v0で始まってv1でおわる,最高vmまで出して良い,t廟の区間
    def calc(v0,v1,vm,t):
        vv = (t-abs(v1-v0))/2+max(v0,v1) #vmを気にしなければどこまで上がれるか
        
        if abs(v1-v0)==t:
            return (v0+v1)*t/2
        elif v1==vm or v0==vm:
            return (v1+v0)*abs(v1-v0)/2 +max(v1,v0)*(t-abs((v1-v0)))
        elif vv<vm:
            return (vv+v0)*(vv-v0)/2 + (vv+v1)*(vv-v1)/2
        else:
            return (v0+vm)*(vm-v0)/2 + vm*(t-(vm-v0)-(vm-v1)) + (vm+v1)*(vm-v1)/2 
         
         
    #区間端での速度,手前から決めていき，無理が生じたら手前を下げていく(Nが小さいので)
    v=[1000]*(N+1)
    v[0]=0
    v[-1]=0
    
    for i in range(N):
        v[i+1]=min(v[i]+t[i],mv[i],mv[i+1])
        if v[i]-v[i+1]>t[i]:#下げきれないなら
            j=i
            while v[j]-v[j+1]>t[j]:
                v[j]=v[j+1]+t[j]
                j-=1
                
                
    ans=0
    for i in range(N):
        ans+=calc(v[i],v[i+1],mv[i],t[i])
    print(ans)
 

main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
t = np.array(['0'] + input().split(), np.int64)
v = list(map(int, input().split()))

# 発車してからn秒後の速度を求める

T = np.cumsum(t).reshape(-1, 1)
arrival = T[-1]
times = np.arange(0, arrival + 0.5, 0.5)
speed_limit = np.minimum(times, times[::-1])

V = np.array(v).reshape(-1, 1)
answer = np.minimum(times, times[::-1])
tmp = np.maximum(T[:-1, :] - times, times - T[1:, :]) + V
tmp = np.maximum(tmp, V)
tmp = tmp.min(axis=0)
answer = np.minimum(tmp, answer)
answer = np.abs(answer[1:] + answer[:-1]) * 0.5 / 2

print(answer.sum())

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
t = np.array(['0'] + input().split(), np.int64)
v = list(map(int, input().split()))

# 発車してからn秒後の速度を求める

T = np.cumsum(t).tolist()
arrival = T[-1]
times = np.arange(0, arrival + 0.5, 0.5)
speed_limit = np.minimum(times, times[::-1])

for i, j, k in zip(T, T[1:], v):
    speed1 = i - times + k
    speed2 = np.full(arrival * 2 + 1, k, np.float)
    speed3 = times - j + k

    speed = np.maximum(speed1, speed3)
    speed = np.maximum(speed2, speed)
    speed_limit = np.minimum(speed_limit, speed)

answer = np.abs(speed_limit[1:] + speed_limit[:-1]) * 0.5 / 2
print(answer.sum())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N = Scanner.int()
    T = Scanner.map_int()
    V = Scanner.map_int()
    T = list(map(lambda x: x * 2, T))
    time = sum(T) + 1
    maxv = [INF] * time
    i = 0
    ct = 0
    for i in range(N):
        for j in range(ct, ct + T[i] + 1):
            maxv[j] = min(V[i], maxv[j])
        ct += T[i]
    maxv[0] = 0
    maxv[-1] = 0
    for t in range(1, time):
        maxv[t] = min(maxv[t], maxv[t-1] + 0.5)
    for t in reversed(range(time - 1)):
        maxv[t] = min(maxv[t], maxv[t + 1] + 0.5)
    print(sum(maxv) * 0.5)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def calc_end_speed(s):
    end_time = e_t[s]
    ma = 10**10
    for i in range(s+1, n):
        ma = min(e_t[i-1] - end_time + v[i], ma)
    return min(e_t[-1] - end_time, v[s], ma)

ans = 0
start_speed = 0

for sect in range(n):
    end_speed = min(calc_end_speed(sect), start_speed+t[sect])
    turn_time = (t[sect]+end_speed-start_speed)/2
    acce_end = min(v[sect]-start_speed, turn_time)
    dece_start = max(t[sect]-(v[sect]-end_speed) ,turn_time)
    max_speed = start_speed+acce_end
    ans += (start_speed+max_speed)*acce_end/2
    ans += max_speed*(dece_start-acce_end)
    ans += (end_speed+max_speed)*(t[sect]-dece_start)/2
    start_speed = end_speed

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
inpl = lambda: list(map(int,input().split()))
N = int(input())
T = [0] + inpl() + [0]
V = [0] + inpl() + [0]
G=deque([]) # t, v
t = 0
for i in range(1,N+2):
    u = V[i]+t
    while G and G[-1][1] >= u:
        G.pop()
    G.append((t,u)) # restrict until t
    t += T[i]
# print(G)

ans = 0
t = 0
y = 0
w, u = G.popleft()
for i in range(1,N+1):
    dt = T[i]
    tN = t + dt
    v = V[i]
    if t >= w:
        w, u = G.popleft()
    tP = t + v - y
    tR = u - v
    tQ = (t + u - y)/2
    # print(tP, tQ, tR)
    if tP >= tR:
        if tN <= tQ:
            ans += (y + dt/2)*dt
            y += dt
        else:
            ans += (y + (tQ-t)/2)*(tQ-t) + (y +tQ-t - (tN-tQ)/2)*(tN-tQ)
            y += (tQ-t) - (tN-tQ)
    else:
        if tN <= tP:
            ans += (y + dt/2)*dt
            y += dt
        elif tN <= tR:
            ans += (y + (tP-t)/2)*(tP-t) + (y+ tP - t)*(tN-tP)
            y = v
        else:
            ans += (y + (tP-t)/2)*(tP-t) + (y+ tP - t)*(tR-tP) + (y+tP-t - (tN-tR)/2)*(tN-tR)
            y = v - (tN-tR)
    t = tN
print(ans)

Submission status: Accepted

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

Ttot = sum(T)
Wf = [0]*(Ttot+1)
Wb = [0]*(Ttot+1)

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

i = 0
w = 0
for t,v in zip(T[::-1],V[::-1]):
    for j in range(t):
        i += 1
        w = min(w+1, v)
        Wb[i] = w

ans = 0
wp = 0
wfp = 0
wbp = Wb[Ttot]
for i in range(1, Ttot+1):
    wf = Wf[i]
    wb = Wb[Ttot-i]
    
    w = min(wf, wb)
    ans += wp + 0.5*(w-wp)
    if wf-wfp==1 and wb-wbp==-1 and w==wp:
        ans += 0.25

    wp = w
    wfp = wf
    wbp = wb

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
L = [0] * (sum(T)*2+1)
R = [0] * (sum(T)*2+1)
xt, xv = 0, 0
for t, v in zip(T, V):
    for tt in range(xt*2+1, (t+xt)*2+1):
        xv += .5
        L[tt] = min(v, xv)
    xt += t
    xv = min(v, xv)
xt, xv = 0, 0
for t, v in zip(T[::-1], V[::-1]):
    for tt in range(xt*2+1, (t+xt)*2+1):
        xv += .5
        R[tt] = min(v, xv)
    xt += t
    xv = min(v, xv)
print(sum(map(min, L, R[::-1]))/2)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
T=sum(t)
d=[0 for _ in range(2*T+2)]
l=[0]
for i in range(n):
    for j in range(t[i]*2):
        l.append(v[i])
l.append(0)
for i in range(2*T):
    d[i+1] = min(d[i]+0.5,l[i+1])

l.reverse()
d2=[0 for _ in range(2*T+2)]

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

d2.reverse()
l.reverse()

d3=[0 for _ in range(2*T+2)]
for i in range(2*T+1):
    d3[i]= min(d[i],d2[i])

res = 0
for i in range(T*2):
    res += (d3[i]+d3[i+1])/4
print(res)

Submission status: Accepted

Solution code:
n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
tTotal = sum(t)*2
speed = [min(i/2,(tTotal-i)/2) for i in range(tTotal+1)]
#?

start=0
end=0
#iter through segments
for i in range(n):
    end += t[i]*2
    for j in range(tTotal+1):
        speed[j] = min(speed[j], v[i] + max(0, -(j-start)/2, (j-end)/2))
    start = end

print(sum(speed)/2)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
# 0.5考慮のため*2、終了時0のため番兵
A = [a*2 for a in LIST()] + [1]
B = [b*2 for b in LIST()] + [0]

def check1(i, t):
    nxtt = cur
    for j in range(i+1, N+1):
        nxtt += A[j-1]
        dist = nxtt - t
        # 1つ先で+1の状態でいても大丈夫かどうか
        if spd + 2 - dist > B[j]:
            return False
    return True

def check2(i, t):
    nxtt = cur
    for j in range(i+1, N+1):
        nxtt += A[j-1]
        dist = nxtt - t
        # 1つ先で今と同じ(+-0)の状態でいても大丈夫かどうか
        if spd + 1 - dist > B[j]:
            return False
    return True

cur = spd = sm = 0
for i, a in enumerate(A[:N]):
    b = B[i]
    # 各時点tにおいて加速、維持が可能かどうか確認
    for t in range(cur, cur+a):
        # 加速OK
        if spd + 1 <= b and check1(i, t):
            # この瞬間の加算分は増減の半分にする
            sm += spd + 0.5
            spd += 1
        # 維持OK
        elif spd <= b and check2(i, t):
            sm += spd
        # 減速必須
        else:
            sm += spd - 0.5
            spd -= 1
    cur += a
print(sm / 4)

Submission status: Accepted

Solution code:
N=int(input())
T=[0]+[int(x) for x in str(input()).split()]+[0]
V=[0]+[int(x) for x in str(input()).split()]+[0]
 
time=0
t=[0]
for i in T:
  time+=i
  t.append(time)
ans=0
 
for j in range(0,2*time):
  m1=1000000000
  m2=1000000000
  t1=j/2
  t2=(j+1)/2
  for i in range(N+2):
    if t1<=t[i]:
      m1=min(m1,V[i]+(t[i]-t1))
    elif t1<=t[i+1]:
      m1=min(m1,V[i])
    else:
      m1=min(m1,V[i]+t1-t[i+1])
 
    if t2<=t[i]:
      m2=min(m2,V[i]+(t[i]-t2))
    elif t2<=t[i+1]:
      m2=min(m2,V[i])
    else:
      m2=min(m2,V[i]+t2-t[i+1])
    
  #print(1,m1,m2)
  ans+=0.25*(m1+m2)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = [2 * int(i) for i in input().split()]
V = [2 * int(i) for i in input().split()]

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

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

for i in range(su):
    A[i + 1] = min(A[i + 1], A[i] + 1)

for i in reversed(range(su)):
    A[i] = min(A[i], A[i + 1] + 1)

print(sum(A) / 4)

Submission status: Accepted

Solution code:
from itertools import chain

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

    vmax = list(chain.from_iterable([i] * (2 * j) for i, j in zip(v, t)))
    vmax = [min(v1,v2) for v1, v2 in zip([0] + vmax, vmax + [0])]

    now = 0
    for i in range(1,len(vmax)):
        vmax[i] = min(vmax[i], now + 0.5)
        now = vmax[i]
    
    now = 0
    for i in range(len(vmax)-1,0,-1):
        vmax[i] = min(vmax[i], now + 0.5)
        now = vmax[i]

    ans = 0
    for i in range(len(vmax)-1):
        if vmax[i] == vmax[i+1]:
            ans += 0.5 * vmax[i]
        else:
            ans += (vmax[i] + vmax[i+1]) * 0.5 / 2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n=int(input())
    tt=LI()
    vv=LI()+[0]
    #区間の変わり目においてのvの最大値を左右から調べる
    y=0
    max_vL=[1000]*(n-1)
    max_vR=[1000]*(n-1)
    for i in range(n-1):
        y=min(vv[i],vv[i+1],y+tt[i])
        max_vL[i]=y
    y=0
    for i in range(n-2,-1,-1):
        y=min(vv[i+1],vv[i],y+tt[i+1])
        max_vR[i]=y
    #print(max_vR)
    #print(max_vL)
    #左右のminを取ることで、変わり目のvを決める
    yy=[0]*(n+1)
    for i in range(n-1):
        yy[i+1]=min(max_vL[i],max_vR[i])
    #print(yy)
    #各区間の面積を求める
    ans=0
    for t,y0,y1,v in zip(tt,yy,yy[1:],vv):
        h=(t+y0+y1)/2
        ans+=((h+y0)*(h-y0)+(h+y1)*(h-y1))/2
        if h>v:ans-=(h-v)**2
    print(ans)

main()

Submission status: Accepted

Solution code:
INF=1<<30
N = int(input())
t = [int(_) for _ in input().split()]
st=[0]*(N+1)
for i in range(N):
    st[i+1]=t[i]+st[i] # st[i] i番目の区間の終了時刻、ただし0番目の区間は時刻0に終了したものとする
T=st[N]
st.append(T)
v = [int(_) for _ in input().split()] # i番目の区間の制限速度
v.insert(0,0)
v.append(0)
l =[0]

now=0.5
ind = 1 # 現在いる区間の番号

while now < T:
    v1=INF
    v2=INF
    for j in range(ind):
        v1=min(v1,v[j]+now-st[j])
    for j in range(ind,N+1):
        v2=min(v2,v[j+1]-now+st[j])
    l.append(min(v[ind],v1,v2))
    now+=0.5
    if now>=st[ind]:
        ind+=1

l.append(0)
res=0

for i in range(len(l)):
    res+=l[i]/2

print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    T=[0]+list(map(int,input().split()))
    for i in range(n): T[i+1]+=T[i]
    V=list(map(int,input().split()))

    def f(t):
        res=INF
        res=min(res,t)
        res=min(res,-t+T[-1])
        for i in range(1,n+1):
            if(t<T[i-1]): res=min(res,-t+T[i-1]+V[i-1])
            elif(t<=T[i]): res=min(res,V[i-1])
            else: res=min(res,t-T[i]+V[i-1])
        return res

    ans=0
    for t in range(2*T[-1]): # 0.5刻みで計算
        ans+=(f(t/2)+f((t+1)/2))/4
    print(ans)
resolve()

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

T.append(0)
V.append(0)
time = [0]*(N+1)
time[0] = T[0]
for i in range(N):
    time[i+1] = time[i]+T[i+1]
    
L = [0]*(2*time[-1]+1)
i = 0
t = 0.5
while t <= time[-1]:
    num = V[i]
    if t == time[i]:
        i += 1
        num = min(num, V[i])
        
    v = L[int(2*t)-1]+0.5
    while v > num:
        v -= 0.5
        
    for j in range(int(i)+1, N+1):
        if v-0.5-V[j] > time[j-1]-t:
            v -= 1
        elif v-V[j] > time[j-1]-t:
            v -= 0.5
        
    L[int(2*t)] = v
    t += 0.5

ans = 0
for i in range(len(L)-1):
    if L[i+1] > L[i]:
        ans += L[i]*0.5+0.25
    elif L[i+1] == L[i]:
        ans += L[i]*0.5
    else:
        ans += L[i]*0.5-0.25
        
print(ans)