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 math
import numpy as np
import decimal
import collections
import itertools
import sys
import random

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]


def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True

def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res

mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod

def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res

class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)

def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res

def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(self.s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and self.s[i - j] == self.s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k

def mod_sqrt(a, p):
    if a == 0:
        return 0
    if p == 2:
        return 1
    k = (p - 1) // 2
    if pow(a, k, p) != 1:
        return -1
    while True:
        n = random.randint(2, p - 1)
        r = (n ** 2 - a) % p
        if r == 0:
            return n
        if pow(r, k, p) == p - 1:
            break
    k += 1
    w, x, y, z = n, 1, 1, 0
    while k:
        if k % 2:
            y, z = w * y + r * x * z, x * y + w * z
        w, x = w * w + r * x * x, 2 * w * x
        w %= p
        x %= p
        y %= p
        z %= p
        k >>= 1
    return y
n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
s_t = sum(t)
ans = [0]
for i in range(n):
    ans[-1] = min(ans[-1], v[i])
    for j in range(t[i] * 2):
        ans.append(v[i])
ans.pop()
ans.append(0)
for i in range(1, s_t * 2 + 1):
    ans[i] = min(ans[i - 1] + 1 / 2, ans[i])
for i in range(1, s_t * 2 + 1)[::-1]:
    ans[i - 1] = min(ans[i] + 1 / 2, ans[i - 1])
print(sum(ans) / 2)

Solution (Python):
from bisect import bisect_left, bisect_right
from itertools import accumulate

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

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


def solve(begin, end, v):
    
    if begin >= end:
        return 0
    if begin + 1 == end:
        if v < vs[bisect_right(Ts, begin) - 1]:
            return 0.25
        else:
            return 0
    min_v = min(vs[bisect_right(Ts, begin) - 1:bisect_left(Ts, end)])
    if min_v == v:
        ret = 0
        last = begin
        for i in range(bisect_right(Ts, begin) - 1, bisect_left(Ts, end)):
            if v == vs[i]:
                ret += solve(last, Ts[i], v)
                last = Ts[i + 1]
        ret += solve(last, end, v)
        return ret
    else:
        return end - begin - 1 + solve(begin + 1, end - 1, v + 1)

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

Solution (Python):
from collections import deque

def main():
    with open(0) as f:
        N, *Temp = map(int, f.read().split())
        T, V = Temp[:N], Temp[N:]
        del Temp
    
    v_left = deque([0]) 
    v_right = deque([0]) 
    
    
    now = 0
    for t,v in zip(T, V):
        now = min(now+t, v)
        v_left.append(now)
    now = 0
    for t, v in zip(reversed(T), reversed(V)):
        now = min(now+t, v)
        v_right.appendleft(now)

    BC = [min(x,y) for x,y in zip(v_left, v_right)] 
    
    S = [squareMeasure(vin, vout, vsup, t) for vin, vout, vsup, t in zip(BC[:N], BC[1:], V, T)]
    ans = sum(S)/2
    print(ans)

def squareMeasure(vin, vout, vsup, t):
    vmax = (t+vout+vin)/2 
    if vmax > vsup:
        a, b = vsup-vin, t+vout-vsup 
        S = (vin+vsup)*a + 2*(b-a)*vsup + (vsup+vout)*(t-b)
    else:
        S = (vin+vmax)*(vmax-vin) + (vmax+vout)*(t+vin-vmax)
    return S 

if __name__ == '__main__':
    main()

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


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

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


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

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

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

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

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

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

print(ans)

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


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

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


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

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

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

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque

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



def make_cumulative(A):
    C = [0] * (len(A) + 1)
    for i, a in enumerate(A):
        i += 1
        C[i] = C[i - 1] + a
    return C


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

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


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

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

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

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

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

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

    print(ans)


if __name__ == "__main__":
    main()

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

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

ans[-1] = 0

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

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

print(sum(ans)/2)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


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

max_v = [0]*(N+1)  
for i in range(N-1):
    max_v[i+1] = min(v[i],v[i+1],max_v[i]+t[i])
for i in range(N-2,-1,-1):
    max_v[i+1] = min(max_v[i+1],v[i],v[i+1],max_v[i+2]+t[i+1])

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

print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


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

max_v = [0]*(N+1)  
for i in range(N-1):
    max_v[i+1] = min(v[i],v[i+1],max_v[i]+t[i])
for i in range(N-2,-1,-1):
    max_v[i+1] = min(max_v[i+1],v[i],v[i+1],max_v[i+2]+t[i+1])

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

print(ans)

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

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

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

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

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


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

    vs[i] = min(prv+1, v[ind], min((l1[j][1]+(l1[j][0]-i)*0.5) for j in range(ind1+1,len(l1))),
                   min((l2[j][1]+(i-l2[j][0])*0.5) for j in range(ind2+1)))
    prv = vs[i]
vs.append(0)
ans = 0
for i in range(len(vs)-1):
    ans += (vs[i]+vs[i+1])/2
print(ans/2)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

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

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


    print(sum(sp)/2)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
def get_current_v_max(t, t_from, t_to, v_max):
    
    if t <= t_from:
        return - t + t_from + v_max
    elif t_to <= t:
        return t - t_to + v_max
    else:
        return v_max


def main():
    N = int(input())
    
    
    SCALE = 2
    T = list(map(lambda t: int(t) * SCALE, input().split()))
    V = list(map(lambda v: int(v) * SCALE, input().split()))
    MAX_V = 100 * SCALE
    
    constraint_list = [(0, 0, 0)]
    t_from = 0
    for t, v in zip(T, V):
        constraint_list.append((t_from, t_from + t, v))
        t_from += t
    constraint_list.append((t_from, t_from, 0))
    
    v_max_list = [MAX_V] * (sum(T) + 1)
    for t in range(sum(T) + 1):
        for t_from, t_to, v_max in constraint_list:
            v_max_list[t] = min(v_max_list[t], get_current_v_max(t, t_from, t_to, v_max))
    
    ans = 0
    for t in range(sum(T)):
        ans += (v_max_list[t] + v_max_list[t + 1]) / 2
    print(ans / (SCALE**2))


if __name__ == '__main__':
    main()

Solution (Python):
"""
dp[t][v] = 時刻tに速度vで走っている時の今までの走行距離の最大値
dp[0][0] = 0, dp[0][i] = -inf(i>0)
条件を考える
  dp[t][v]について、時刻tにおける速度の最大値をM(t)とすると、
  v >  M[t] -> dp[v][t] = -inf
  v <= M[t] -> dp[v][t] = max(dp[t-1][v+1]+(2*v+1)/2, dp[t-1][v]+v, dp[t-1][v-1]+(2*v-1)/2)
ans = max(dp[sum(T)])
"""
from itertools import accumulate
U = 300
n = int(input())
T = [0] + list(map(lambda x:int(x)*2, input().split()))
V = list(map(lambda x:int(x)*2, input().split())) + [0]
S = sum(T)
M = [0]*(S+1)
K = list(accumulate(T))
for i in range(n):
  for j in range(K[i]+1, K[i+1]):
    M[j] = V[i]
  M[K[i+1]] = min(V[i], V[i+1])
dp = [[-float("inf")]*(U+1) for _ in range(S+1)]
dp[0][0] = 0
for t in range(1, S+1):
  for v in range(U+1):
    if v > M[t]:
      continue
    dp[t][v] = dp[t-1][v] + v
    if v > 0:
      dp[t][v] = max(dp[t][v], dp[t-1][v-1]+(2*v-1)/2)
    if v < U:
      dp[t][v] = max(dp[t][v], dp[t-1][v+1]+(2*v+1)/2)
ans = max(dp[S]) / 4
print(ans)

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 = list(map(float, input().split()))
v = list(map(float, input().split()))

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

v.append(0.0)

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

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

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

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

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

ans /= 4.0

print(ans)

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

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


dp = [[-float('inf')]*201 for _ in range(sumt*2+1)]
dp[0][0] = 0
for i in range(1, len(dp)):
    maxj = min(sv[i], sv[i+1])*2
    for j in range(len(dp[i])):
        k = 0.25*j
        
        if j <= maxj:
            dp[i][j] = max(dp[i][j], dp[i-1][j]+k)
        
        if (j+1) <= maxj:
            dp[i][j+1] = max(dp[i][j+1], dp[i-1][j]+k+0.25)
        
        if j > 0 and (j-1) <= maxj:
            dp[i][j-1] = max(dp[i][j-1], dp[i-1][j]+k-0.25)

print(dp[-1][0])

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

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


dp = [[-float('inf')]*201 for _ in range(sumt*2+1)]
dp[0][0] = 0
for i in range(1, len(dp)):
    maxj = min(sv[i], sv[i+1])*2
    for j in range(len(dp[i])):
        k = 0.25*j
        
        if j <= maxj:
            dp[i][j] = max(dp[i][j], dp[i-1][j]+k)
        
        if (j+1) <= maxj:
            dp[i][j+1] = max(dp[i][j+1], dp[i-1][j]+k+0.25)
        
        if j > 0 and (j-1) <= maxj:
            dp[i][j-1] = max(dp[i][j-1], dp[i-1][j]+k-0.25)

print(dp[-1][0])

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

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

if __name__=='__main__':
    main()

Solution (Python):
ADJ = 10**2
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
for i in range(n):
    ts[i] *= ADJ
    vs[i] *= ADJ
tt = sum(ts)
vss = [0]*tt
j = 0
cnt = 0
for i in range(tt):
    vss[i] = vs[j]
    cnt += 1
    if cnt == ts[j]:
        j += 1
        cnt = 0

max_speed = 1
max_speeds = [0]*tt
for i in reversed(range(tt-1)):
    max_speeds[i] = min(max_speed,vss[i],vss[i+1],max_speeds[i+1]+1)
    max_speed += 1

cv = 0
for i in range(tt):
    if cv < max_speeds[i]:
        cv += 1
    elif cv == max_speeds[i]:
        pass
    else:
        cv -= 1
    vss[i] = cv

res = 0
for i in range(tt):
    if i == 0:
        res += vss[i] / 2
    else:
        if vss[i] >= vss[i-1]:
            res += vss[i-1] + (vss[i] - vss[i-1]) / 2
        else:
            res += (vss[i-1] - vss[i]) / 2 + vss[i]
    
    
print(res/ADJ/ADJ)

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

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


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

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

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


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

if __name__ == "__main__":
    main()

Solution (Python):
"""
ABC076_D AtCoderExpress
まず区間に注目してEditorialみたいなグラフを思い描くことがきつかった。
そのうえで、区間Limitをバグなく実装するのが結構ポイント。
あとはVVあたりがバグってないかをPrintしながら見ていく形。
"""
N = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))
TMAX = sum(T)

TS = [0] * (N+1)
for i in range(N):
  TS[i+1] = TS[i] + T[i]
T_Left = TS[:N]
T_Right = TS[1:]






VV = [min(i*0.5, (TMAX*2-i) * 0.5) for i in range(TMAX*2+1)]



for i in range(N):
  for tt in range(TMAX*2+1):
    VV[tt] = min(VV[tt], V[i] + max(0, (T_Left[i]*2 - tt) * 0.5, (tt-T_Right[i]*2) * 0.5))



print(sum(VV)/2)

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

T=sum(t)
ans=[0]

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

ans[-1]=0

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

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

print(sum(ans)/2)