Problem:


﻿Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

1 \leq N \leq 100

1 \leq t_i \leq 200

1 \leq v_i \leq 100

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
t_1 t_2 t_3 … t_N
v_1 v_2 v_3 … v_N

Output

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

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

Sample Input 1

1
100
30

Sample Output 1

2100.000000000000000

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

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

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

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

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

Sample Input 2

2
60 50
34 38

Sample Output 2

2632.000000000000000

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

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

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

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

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

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

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

Sample Input 3

3
12 14 2
6 2 7

Sample Output 3

76.000000000000000

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

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

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

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

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

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

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

Sample Input 4

1
9
10

Sample Output 4

20.250000000000000000

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

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

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

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

Sample Input 5

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

Sample Output 5

20291.000000000000



Sample input:
1
100
30


Sample output:
2100.000000000000000

Submission status: Wrong Answer

Solution code:
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)  # 0秒後,t1秒後,t1+t2秒後,…の時点で出せる最大速度
for i in range(N-1):
    max_v[i+1] = min(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],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)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = [int(t) for t in input().split()]
v = [int(v) for v in input().split()]
#各区間でvin,voutが決まる。それを境界条件として各区間での最大走行距離を求める。
ans = 0
vin = 0
v.append(0)
for i in range(N):
    if v[i] < v[i+1]:
        if vin + t[i] <= v[i]:
            vout = vin + t[i]
        else:
            vout = v[i]
    else:
        vout = v[i+1]
    #走行時間Tとして、v=t+vin, v=-(t-T)+vout, 0<=v<=v[i]で囲まれる面積が最大走行距離
    crossT = (t[i] +vout -vin)/2 #交点のt
    if crossT + vin > v[i] and 0 < crossT < t[i]: #上限速度に到達する場合
        ans += (vin + crossT + vin)*crossT + (vout + crossT + vin)*(t[i]-crossT) - (crossT + vin - v[i])*(t[i] + vout + vin - 2*v[i]) #台形＋台形-余剰三角形(誤差軽減のため後で2で割る)
    else:
        ans += (vin + crossT + vin)*crossT + (vout + crossT + vin)*(t[i]-crossT)
    vin = vout
ans /= 2
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = [int(t) for t in input().split()]
v = [int(v) for v in input().split()]
#各区間でvin,voutが決まる。それを境界条件として各区間での最大走行距離を求める。
ans = 0
vin = 0
v.append(0)
for i in range(N):
    if v[i] < v[i+1]:
        if vin + t[i] <= v[i]:
            vout = vin + t[i]
        else:
            vout = v[i]
    else:
        vout = v[i+1]
    #走行時間Tとして、v=t+vin, v=-(t-T)+vout, 0<=v<=v[i]で囲まれる面積が最大走行距離
    crossT = (t[i] +vout -vin)/2 #交点のt
    if crossT + vin > v[i] and 0 < crossT < t[i]: #上限速度に到達する場合
        ans += (vin + crossT + vin)*crossT/2 + (vout + crossT + vin)*(t[i]-crossT)/2 - (crossT + vin - v[i])*(t[i] + vout + vin - 2*v[i])/2 #台形＋台形-余剰三角形
    else:
        ans += (vin + crossT + vin)*crossT/2 + (vout + crossT + vin)*(t[i]-crossT)/2
    vin = vout
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = [int(t) for t in input().split()]
v = [int(v) for v in input().split()]
#各区間でvin,voutが決まる。それを境界条件として各区間での最大走行距離を求める。
import scipy.integrate as itgr
#積分用のvの関数
def vfunc(t,vin, vout, supv, T):
    if 2*t <= (T + vout - vin):
        v = t + vin
    else:
        v = - t + T + vout
    if v > supv:
        v = supv
    return v

ans = 0
vin = 0
v.append(0)
for i in range(N):
    if v[i] < v[i+1]:
        if vin + t[i] <= v[i]:
            vout = vin + t[i]
        else:
            vout = v[i]
    else:
        vout = v[i+1]
    #走行時間Tとして、v=t+vin, v=-(t-T)+vout, 0<=v<=v[i]で囲まれる面積が最大走行距離
    I = itgr.quad(vfunc, 0, t[i], args=(vin,vout,v[i],t[i]))
    ans += I[0]
    vin = vout
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = [int(t) for t in input().split()]
v = [int(v) for v in input().split()]
#各区間でvin,voutが決まる。それを境界条件として各区間での最大走行距離を求める。
import scipy.integrate as itgr
#積分用のvの関数
def vfunc(t,vin, vout, supv, T):
    if t <= (T + vout - vin) / 2:
        v = t + vin
    else:
        v = - t + T + vout
    if v > supv:
        v = supv
    return v

ans = 0
vin = 0
v.append(0)
for i in range(N):
    if v[i] < v[i+1]:
        if vin + t[i] <= v[i]:
            vout = vin + t[i]
        else:
            vout = v[i]
    else:
        vout = v[i+1]
    #走行時間Tとして、v=t+vin, v=-(t-T)+vout, 0<=v<=v[i]で囲まれる面積が最大走行距離
    I = itgr.quad(vfunc, 0, t[i], args=(vin,vout,v[i],t[i]))
    ans += I[0]
    vin = vout
print(ans)

Submission status: Wrong Answer

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N = iIn()
T = iInLH()
V = iInLH()

## 終状態は停止
V.append(0)

## 初期値
v = 0
x = 0
for i in range(N):
    t_rest = T[i]
    while t_rest > 0:
        ## 次の速度を求める
        v_next = min(v+0.5, V[i], V[i+1]+t_rest-0.5)
        
        ## 状態の更新
        x += (v + v_next) / 4.0
        v = v_next
        t_rest -= 0.5

        #print(v, x, t_rest)

print(x)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    T = list(mi())
    V = list(mi())

    if N == 1:
        t,v =T[0],V[0]
        ans = (t-v)*v
        if ans < 0:
            ans = t**2/4
        
        print(ans)
        exit()


    acce_areas = 0
    pre_v = 0
    for i in range(N):
        v = V[i]
        acce_areas += (v+pre_v) * abs(v-pre_v) / 2
        pre_v = v
    
    V.append(0)
    T.append(0)


    pre_v = 0
    rect_sums = 0
    for i in range(N):
        v,t = V[i],T[i]
        next_v = V[i+1]

        dv1 = abs(v - pre_v)
        dv2 = abs(next_v - v)

        lu = pre_v < v
        ld = not lu

        ru = v < next_v
        rd = not ru

        bottom = 0
        if lu and rd:
            bottom += t-(dv1+dv2)
        if ld and ru:
            bottom += t
        if lu and ru:
            bottom += t-dv1
        if ld and rd:
            bottom += t-dv2

        rect_sums += bottom * v
        pre_v = v

    ans = acce_areas + rect_sums + V[-2] ** 2 / 2

    print(ans)

    



    # ans = 0
    # pre_v = 0
    # pre_is_up = True
    # for i in range(N-1):
    #     up = V[i] < V[i+1]

    #     t,v = T[i],V[i]
    #     acce_area = (v+pre_v) * abs(v-pre_v) / 2

    #     if up:
    #         rect_area = (t-abs(v-pre_v))*v
    #     else:
    #         rect_area = (t-abs(v-pre_v) - abs(V[i+1]-v))*v
        
    #     if 

    #     ans += acce_area + rect_area
    #     pre_v = v
    #     pre_is_up = up

    # acce_area = (v+pre_v) * abs(v-pre_v) / 2
    # rect_area = (t-abs(v-pre_v) - v)*v
    # trig_area = v**2 / 2
    # ans += acce_area + rect_area + trig_area











if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n=int(readline())
    t,v=(list(map(int,l.split())) for l in read().splitlines())
    vi=[(x,i+1) for i,x in enumerate(v)]
    x=[0]*(n+2)
    y=[0]*(n+2)
    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:
        #print(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)
        y[_i_-1]=min(h,x[_i_]-sx+sy)
        dw=gx-sx
        dh=abs(gy-sy)
        be=dw-dh
        ht=min(h-sy,h-gy,be/2)
        te=max(0,be-2*ht)
        ans+=(te+be)*ht/2
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n=int(readline())
    t,v=(list(map(int,l.split())) for l in read().splitlines())
    vi=[(x,i+1) for i,x in enumerate(v)]
    x=[0]*(n+2)
    y=[0]*(n+2)
    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:
        #print(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)
        y[_i_-1]=min(h,x[_i_]-sx+gx)
        dw=gx-sx
        dh=abs(gy-sy)
        be=dw-dh
        ht=min(h-sy,h-gy,be/2)
        te=max(0,be-2*ht)
        ans+=(te+be)*ht/2
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n=int(readline())
    t,v=(list(map(int,l.split())) for l in read().splitlines())
    vi=[(x,i+1) for i,x in enumerate(v)]
    x=[0]*(n+2)
    y=[0]*(n+2)
    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:
        print(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)
        y[_i_-1]=min(h,x[_i_]-sx+gx)
        dw=gx-sx
        dh=abs(gy-sy)
        be=dw-dh
        ht=min(h-sy,h-gy,be/2)
        te=max(0,be-2*ht)
        ans+=(te+be)*ht/2
    print(ans)

if __name__=='__main__':
    main()
        #if 0<-dh<dw:
        #    stk.append(s[0]+min((dw+dh)/2,h-s[1]))
        #    stk.append(g[0]-min(-dh+(dw+dh)/2,h-g[1])
        #    ans+=(-dh
        #elif 0<dh<dw:
        #    stk.append(s[0]+min(dh+(dw-dh)/2,h-s[1]))
        #    stk.append(g[0]-min((dw-dh)/2,h-g[1])
        #elif -dh>=w
        #    stk.append(g[0])
        #    stk.append(g[0])
        #elif dh>=w:
        #    stk.append(s[0])
        #    stk.append(s[0])

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop
from bisect import bisect_left, 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)
    x[0]=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])
        _i=memo[bisect_left(memo,e[1])-1]
        i_=memo[bisect_left(memo,e[1])+1]
        sx=x[_i]
        gx=x[i_-1]
        sy=v[_i]
        gy=v[i_]
        h=e[0]
        dw=gx-sx
        dh=abs(gy-sy)
        if 0<=dh<=dw:
            be=dw-dh
            ht=min(h-sy,h-gy,be/2)
            te=max(0,dw-dh-2*ht)
            ans+=(te+be)*ht/2
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

TALL = sum(T)

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

for i in range(N):
  start_time = ACCT[i]
  vmax = V[i]
  if i != N-1:
    next_vmax = V[i+1]
  else:
    next_vmax = 0
  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)
ans = 0
for i in range(TALL*2):
  ans += Lspeed[i]+Lspeed[i+1]
print(ans/4)

Submission status: Wrong Answer

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if __name__ == "__main__":
    main()