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

Solution (Python):
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)

Solution (Python):
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]
        
        for k in range(j,i,-1):
            if mnow + t[k] <= v[k]:
                mnow += t[k]
            else:
                mnow = v[k]
            
        m = min(m,mnow)
        t0 += t[j]
    m = min(m,nowv+t[i])
    
    if m == v[i]:
        if nowv+t[i] <= v[i]:
            ans += (2*nowv+t[i])*t[i]/2
        else:
            
            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
                
            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
    
    nowv = m
    
print(ans)

Solution (Python):
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)

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))
  
  dp[i + 1] = min(ok, r)

ps.add((0, 0))
ps.add((cst[-1], 0))

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)

Solution (Python):
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
        
        p = (prev_v + cur_v) * 0.5 / 2
        area += p
        cur_t += 0.5
    print(area)
main()

Solution (Python):


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
    
    for i in range(N-1):
        t[i+1]+=t[i]
    t.append(0)
        
    vt=[1000]*T    
        
    
    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()


"""


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)
    
    
    
    
    def calc(v0,v1,vm,t):
        vv = (t-abs(v1-v0))/2+max(v0,v1) 
        
        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 
         
         
    
    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()


"""

Solution (Python):

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)
    
    
    
    
    def calc(v0,v1,vm,t):
        vv = (t-abs(v1-v0))/2+max(v0,v1) 
        
        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 
         
         
    
    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()

Solution (Python):
import numpy as np

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



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())

Solution (Python):
import numpy as np

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



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())

Solution (Python):

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():
    
    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()

Solution (Python):
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)

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

time = 0
sum_t = sum(t)
velo_cap =[float("inf")]*(2*sum_t+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum_t+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum_t+1):
  velo_cap[s] = min(velo_cap[s],2*sum_t-s,s)


print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)

Solution (Python):
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 = 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)) 
    t += T[i]


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
    
    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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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

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)

Solution (Python):


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()

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
        
        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
        
        if spd + 1 - dist > B[j]:
            return False
    return True

cur = spd = sm = 0
for i, a in enumerate(A[:N]):
    b = B[i]
    
    for t in range(cur, cur+a):
        
        if spd + 1 <= b and check1(i, t):
            
            sm += spd + 0.5
            spd += 1
        
        elif spd <= b and check2(i, t):
            sm += spd
        
        else:
            sm += spd - 0.5
            spd -= 1
    cur += a
print(sm / 4)

Solution (Python):
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])
    
  
  ans+=0.25*(m1+m2)
print(ans)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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]
    
    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
    
    
    
    yy=[0]*(n+1)
    for i in range(n-1):
        yy[i+1]=min(max_vL[i],max_vR[i])
    
    
    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()

Solution (Python):
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] 
T=st[N]
st.append(T)
v = [int(_) for _ in input().split()] 
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)

Solution (Python):
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]): 
        ans+=(f(t/2)+f((t+1)/2))/4
    print(ans)
resolve()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
t = LI()
v = LI()
T = sum(t)*2
vcandi =[[0]*(N+2) for _ in range(T+1)]
sumt = int(0)
for i in range(N):
    time = t[i]*2
    for j in range(sumt):
        vcandi[j][i] = v[i]+(sumt-j)*0.5
    for j in range(time+1):
        vcandi[sumt+j][i] = v[i]
    sumt = sumt+time
    for j in range(T-sumt+1):
        vcandi[sumt+j][i] = v[i]+j*0.5
for i in range(T+1):
    vcandi[i][N] = i*0.5
    vcandi[i][N+1] = (T-i)*0.5
ansV =[0]*(T+1)
for i in range(T+1):
    ansV[i] = min(vcandi[i])


cur = float(0)
for i in range(T):
    cur += (ansV[i]+ansV[i+1])/2*0.5

ans = cur
print(ans)

Solution (Python):
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))+[0]
V=max(v)
dp=[[0]]+[[] for i in range(V)]
for i in range(0,n):
    a=t[i]
    b=v[i]
    c=v[i+1]
    h=[[] for j in range(V+1)]
    for j in range(V+1):
        l=V-j
        if dp[l]:
            if max(0,l-a)<=min(b,l+a):
                for k in range(max(0,l-a),min(b,c,l+a)+1):
                    if not h[k]:
                        h[k]=dp[l]+[k]
    dp=h
ans=0
for i in range(n):
    a=t[i]
    b=v[i]
    v1=dp[0][i]
    v2=dp[0][i+1]
    if v1==v2==b:
        ans+=a*b
    elif v1==b:
        ans+=a*b-(b-v2)**2/2
    elif v2==b:
        ans+=a*b-(b-v1)**2/2
    else:
        if 2*b-v1-v2<=a:
            ans+=a*b-(b-v2)**2/2-(b-v1)**2/2
        else:
            ans+=a*a/2+a*v1-(a+v1-v2)**2/4
print(ans)

Solution (Python):
n = int(input())
list_t = list(map(int, input().split()))
list_v = list(map(int, input().split()))

list_v2 = [0 for i in range(n+1)]
list_t.append(0)
list_v.append(0)
for i in range(n-1)[::-1]:
  list_v2[i] = min(list_v[i], list_v[i+1], list_v2[i+1] + list_t[i+1])

dist = 0
v0 = 0
for i in range(n):
  t1 = min(list_v[i] - v0, (list_t[i] - (v0 - list_v2[i])) / 2, list_t[i])
  t2 = max(v0 + t1 - list_v2[i], 0)
  dist += (2*v0+t1)*t1/2 + (v0+t1)*(list_t[i]-t1-t2) + (2*(v0+t1)-t2)*t2/2
  v0 = v0 + t1 - t2
print(dist)

Solution (Python):
def solve():
  n=int(input())
  arr1=list(map(int,input().split()))
  arr2=list(map(int,input().split()))
  tlist=[0]
  for val in arr1:
    tlist.append(tlist[-1]+val)
  t=tlist[-1]
  ans=0
  for i in range(1,2*t):
    tt=i/2
    tmp=10**18
    for j in range(n):
      if tt<=tlist[j]:
        tmp=min(tmp,arr2[j]+(tlist[j]-tt))
      elif tlist[j+1]<=tt:
        tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
      else:
        tmp=min(tmp,arr2[j])
    tmp=min(tmp,tt)
    tmp=min(tmp,t-tt)
    ans+=tmp
  print(ans/2)
solve()

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    t = list(map(lambda x: int(x) * 2, input().split()))
    v = list(map(float, input().split())) + [0]

    for i in range(1, N):
        t[i] += t[i-1]
    t += [t[-1]]
    vnow = [0.0] * (t[-1] + 1)
    vr = [0.0] * (t[-1] + 1)
    r = 0
    for i in range(1, len(vr)):
        if i < t[r]:
            vr[i] = v[r]
        elif i == t[r]:
            vr[i] = min(v[r], v[r+1])
            r += 1
        vnow[i] = min(vnow[i-1] + 0.5, vr[i])
    for i in range(len(vr)-2, -1, -1):
        vnow[i] = min(vnow[i], vnow[i+1] + 0.5)
    
    print(sum(vnow) / 2)

if __name__ == "__main__":
    main()

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


V = [100] * (2*sum(t) + 1)
T = 0
for i in range(N):
    for j in range(T+1, T+t[i]*2+1):
        V[j] = min(V[j], v[i])
    T += t[i]*2

for i in range(min(len(V), 201)):
    V[i] = min(V[i], i*0.5)
for i in range(min(len(V), 201)):
    V[-i-1] = min(V[-i-1], i*0.5)
V
T = 0
for i in range(N-1):
    T += t[i]*2
    vi = min(V[T], v[i], v[i+1])
    for j in range(201):
        if T-j >= 0:
            V[T-j] = min(V[T-j], vi+0.5*j)
        if T+j <= len(V)-1:
            V[T+j] = min(V[T+j], vi+0.5*j)

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

Solution (Python):
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
x=[0]
for i in range(n):x+=[v[i]]*t[i]*2
x+=[0]
l=[min(x[i],x[i+1])for i in range(len(x)-1)]
for i in range(1,len(l)):l[i]=min(l[i],l[i-1]+0.5)
for i in range(len(l)-2,-1,-1):l[i]=min(l[i],l[i+1]+0.5)
print(sum(0.25*(l[i]+l[i-1])for i in range(1,len(l))))

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

st = [0]
s = 0
for i in range(N):
    s+=t[i]
    st.append(s)

T = st[N]
i = 0
max_v = [0]
while i<=T:
    mv = 10**28
    for j in range(N):
        if i<st[j]:
            mv = min(v[j]+st[j]-i,mv)
        elif i>st[j+1]:
            mv = min(v[j]+i-st[j+1],mv)
        else:
            mv = min(v[j],mv)
    mv = min(T-i,i,mv)
    max_v.append(mv)
    i+=0.5

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

print(ans)