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
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


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


def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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





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)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


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


def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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





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)

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

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

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

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

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




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

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

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

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

Solution (Python):

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[0][0] = 0

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

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

    bef_bound = vel[bef-1]  
    bound = vel[phase-1]    
    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:
                
                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)

Solution (Python):

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[0][0] = 0

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

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

    bef_bound = vel[bef-1]  
    bound = vel[phase-1]    
    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:
                
                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)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


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
    

    N = int(input())
    
    ts = tuple(map(int, input().split())) 
    
    

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



        


if __name__ == "__main__":
    main()

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

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

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

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

Solution (Python):

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

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

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

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

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

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

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

Solution (Python):
def main():
	n = int(input())
	*t, = map(int, input().split())
	tot = sum(t)
	*v, = map(int, input().split())
	lim1 = []
	lim2 = [(1, 0, 0), (-1, tot, tot)]
	til = 0
	for t1, t2, v1 in zip([0] + t, t, v):
		lim1.append((til, til + t2, v1))
		lim2.append((-1, til, til + v1))
		lim2.append((1, til + t2, v1 - (til + t2)))
		til += t2

	def mi(time):
		ret = float("inf")
		for l, r, lim in lim1:
			if l <= time <= r:
				ret = min(ret, lim)
		for f, tt, y in lim2:
			if f == -1 and time <= tt:
				ret = min(ret, y - time)
			if f == 1 and time >= tt:
				ret = min(ret, time + y)
		return ret

	print(sum(mi(i / 2) for i in range(tot * 2 + 1)) / 2)

if __name__ == '__main__':
	main()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S = 0

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

print(S / 8)

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