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:
n = int(input())
T = list(map(int, input().split()))
V = [0] + list(map(int, input().split())) + [0]

acumT = [0] * (n + 1)
for i in range(n):
  acumT[i+1] = acumT[i] + T[i]

PV = [0] * (sum(T) * 10 + 1)
for (t1, t2), (v1, v2, v3) in zip(zip(acumT, acumT[1:]), zip(V, V[1:], V[2:])):
  for i in range(t1 * 10, t2 * 10 + 1):
    ii = i / 10 
    PV[i] = min(ii, -ii + sum(T), v2, ii - t1 + v1, -ii + t2 + v3)

area = sum((i + j) * 0.1 / 2 for i, j in zip(PV, PV[1:]))  
print(area)

Submission status: Wrong Answer

Solution code:
n = int(input())
T = list(map(int, input().split()))
V = [0] + list(map(int, input().split())) + [0]

acumT = [0] * (n + 1)
for i in range(n):
  acumT[i+1] = acumT[i] + T[i]

PV = [0] * (sum(T) * 2 + 1)
for (t1, t2), (v1, v2, v3) in zip(zip(acumT, acumT[1:]), zip(V, V[1:], V[2:])):
  for i in range(t1*2, t2*2 + 1):
    ii = i / 2 
    PV[i] = min(ii, -ii + sum(T), v2, ii - t1 + v1, -ii + t2 + v3)

area = sum((i + j) * 0.5 / 2 for i, j in zip(PV, PV[1:]))  
print(area)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

main()

Submission status: Wrong Answer

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

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

main()

Submission status: Wrong Answer

Solution code:


def calc(last_v, next_v, v_i, t_i):
    t1, t2 = (next_v - last_v + t_i) * 0.5, (last_v - next_v + t_i) * 0.5
    t1, t2 = max(0, t1), max(0, t2)
    cur_v = min(v_i, last_v + t1)
    t1, t2 = max(cur_v - last_v, 0), max(cur_v - next_v, 0)
    dist = t1 * (2 * last_v + t1) * 0.5 \
        + t2 * (2 * next_v + t2) * 0.5\
        + (t_i - t1 - t2) * cur_v
    return dist, cur_v - t2


n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))

dist = 0
last_v = 0
for i in range(n-1):
    cur_dist, last_v = calc(last_v, v[i + 1], v[i], t[i])
    dist += cur_dist

cur_dist, _ = calc(last_v, 0, v[-1], t[-1])
dist += cur_dist

print(dist)

Submission status: Wrong Answer

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

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

ans = 0
start_speed = 0

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

print(ans)

Submission status: Wrong Answer

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

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

ans = 0
sect = 0
end_max = calc_max(sect)
now_speed = 0
for now in range(e_t[-1]):
    if now>=e_t[sect]:
        sect += 1
        end_max = calc_max(sect)
    
    new_speed = min(now_speed+1, v[sect], end_max+e_t[sect]-now-1)
    ans += (now_speed + new_speed) / 2
    now_speed = new_speed

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

d2.reverse()
l.reverse()

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

res = 0
for i in range(T):
    v1,v2=d3[i],d3[i+1]
    if v1==v2 and v1<l[i+1] and l[i] <= l[i+1]:
        tres = v1+0.25
    else:
        tres = (v1+v2)/2
    res += tres
print(res)

Submission status: Wrong Answer

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

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

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

d2.reverse()
l.reverse()

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

res = 0
for i in range(T):
    v1,v2=d3[i],d3[i+1]
    if v1==v2 and l[i] <= l[i+1]:
        tres = v1+0.25
    else:
        tres = (v1+v2)/2
    res += tres
print(res)

Submission status: Wrong Answer

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

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

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

d2.reverse()
l.reverse()

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

res = 0
for i in range(T):
    v1,v2=d3[i],d3[i+1]
    if v1==v2 and v1 < l[i+1] and v2 < l[i]:
        tres = v1+0.25
    else:
        tres = (v1+v2)/2
    res += tres
print(res)

Submission status: Wrong Answer

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

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

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

d2.reverse()

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

print((sum(d3[:T])+sum(d3[1:]))/2)

Submission status: Wrong Answer

Solution code:
n = int(input())
times = [int(x) for x in input().split()]
vels = [int(x) for x in input().split()]
sums = 0
result = 0
times2 = [0]
for i in times:
  sums+=i
  times2.append(sums)
vels.append(0)
#times2.append(sums)

state = 'up'
t = 0
v = 0
i=0
markt = 0
markv = 0
#while t<times2[-1]:
while i<n:
  #for j in range(i, n+1):
  for j in range(n, i-1, -1):
    if vels[j]<v and times2[j]-t==v-vels[j]:
      result+=(t-markt)*((v+markv)/2)
      #print((t-markt)*((v+markv)/2), t-markt, (v+markv)/2)
      #print(t, markt, v, markv)
      i = j
      result+=(times2[j]-t)*((v+vels[j])/2)
      #print((times2[j]-t)*((v+vels[j])/2), times2[j]-t, (v+vels[j])/2)
      t = times2[j]
      v = vels[j]
      state = 'stay'
      markt = t
      markv = v
      break
  t+=0.25
  if i==n:
    break
  if t>times2[i+1]:
    #print(t)
    i+=1
    if i>=n:
      break
  #print(v)
  if i>n:
    break
  if state=='up':
    v+=0.25
    if v==vels[i]:
      state='stay'
      result+=(t-markt)*((v+markv)/2)
      #print((t-markt)*((v+markv)/2), t-markt, (v+markv)/2)
      #print(t, markt, v, markv)
      markt = t
      markv = v
  else:
    if vels[i]>v:
      state='up'
      result+=(t-markt-0.25)*v
      #print((t-markt-0.5)*v, t-markt-0.5, v)
      markt = t-0.25
      v+=0.25
  
  

print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
times = [int(x) for x in input().split()]
vels = [int(x) for x in input().split()]
sums = 0
result = 0
times2 = [0]
for i in times:
  sums+=i
  times2.append(sums)
vels.append(0)
#times2.append(sums)

state = 'up'
t = 0
v = 0
i=0
markt = 0
markv = 0
#while t<times2[-1]:
while i<n:
  #for j in range(i, n+1):
  for j in range(n, i-1, -1):
    if vels[j]<v and times2[j]-t==v-vels[j]:
      result+=(t-markt)*((v+markv)/2)
      #print((t-markt)*((v+markv)/2), t-markt, (v+markv)/2)
      #print(t, markt, v, markv)
      i = j
      result+=(times2[j]-t)*((v+vels[j])/2)
      #print((times2[j]-t)*((v+vels[j])/2), times2[j]-t, (v+vels[j])/2)
      t = times2[j]
      v = vels[j]
      state = 'stay'
      markt = t
      markv = v
      break
  t+=0.5
  if i==n:
    break
  if t>times2[i+1]:
    #print(t)
    i+=1
    if i>=n:
      break
  #print(v)
  if i>n:
    break
  if state=='up':
    v+=0.5
    if v==vels[i]:
      state='stay'
      result+=(t-markt)*((v+markv)/2)
      #print((t-markt)*((v+markv)/2), t-markt, (v+markv)/2)
      #print(t, markt, v, markv)
      markt = t
      markv = v
  else:
    if vels[i]>v:
      state='up'
      result+=(t-markt-0.5)*v
      #print((t-markt-0.5)*v, t-markt-0.5, v)
      markt = t-0.5
      v+=0.5
  
  

print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
times = [int(x) for x in input().split()]
vels = [int(x) for x in input().split()]
sums = 0
result = 0
times2 = [0]
for i in times:
  sums+=i
  times2.append(sums)
vels.append(0)
#times2.append(sums)

state = 'up'
t = 0
v = 0
i=0
markt = 0
markv = 0
#while t<times2[-1]:
while i<n:
  for j in range(i, n+1):
    if vels[j]<v and times2[j]-t==v-vels[j]:
      result+=(t-markt)*((v+markv)/2)
      #print((t-markt)*((v+markv)/2), t-markt, (v+markv)/2)
      #print(t, markt, v, markv)
      i = j
      result+=(times2[j]-t)*((v+vels[j])/2)
      #print((times2[j]-t)*((v+vels[j])/2), times2[j]-t, (v+vels[j])/2)
      t = times2[j]
      v = vels[j]
      state = 'stay'
      markt = t
      markv = v
      break
  t+=0.5
  if i==n:
    break
  if t>times2[i+1]:
    #print(t)
    i+=1
    if i>=n:
      break
  #print(v)
  if i>n:
    break
  if state=='up':
    v+=0.5
    if v==vels[i]:
      state='stay'
      result+=(t-markt)*((v+markv)/2)
      #print((t-markt)*((v+markv)/2), t-markt, (v+markv)/2)
      #print(t, markt, v, markv)
      markt = t
      markv = v
  else:
    if vels[i]>v:
      state='up'
      result+=(t-markt-0.5)*v
      #print((t-markt-0.5)*v, t-markt-0.5, v)
      markt = t-0.5
      v+=0.5
  
  

print(result)

Submission status: Wrong Answer

Solution code:
def toPrefixSum(l):
    x = 0
    result = []
    for i in l:
        x += i
        result.append(x)
    return result

n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()] + [0]

tTotal = sum(t)
t = toPrefixSum(t)
currentSegment = 0
speed = 0
ans = 0

for time in range(tTotal*2):
    if time==0: continue
    if time/2 > t[currentSegment]:
        currentSegment += 1

    if speed-v[currentSegment+1] < t[currentSegment]-time/2 and speed<v[currentSegment]:
        speed += 0.5
    elif speed-v[currentSegment+1] > t[currentSegment]-time/2 or speed>v[currentSegment]:
        speed -= 0.5

    ans += speed

print(ans/2)

Submission status: Wrong Answer

Solution code:
N=int(input())
T=[int(x) for x in str(input()).split()]
V=[int(x) for x in str(input()).split()]+[0]



dist=0
speed=0

for i in range(N):
  #print(speed,T[i],V[i],V[i+1])
  if (V[i]>=speed):
    if (V[i]<=V[i+1]):
      if(T[i]>=V[i]-speed):
        dist+=speed*(V[i]-speed)+0.5*(V[i]-speed)**2

        dist+=V[i]*(T[i]-(V[i]-speed))
        speed=V[i]
      else:
        dist+=speed*(T[i])+0.5*(T[i])**2
        speed+=T[i]
    else:
      #print("123")
      if (T[i]>=V[i]-speed+V[i]-V[i+1]):
        #print("Hello")
        dist+=speed*(V[i]-speed)+0.5*(V[i]-speed)**2
        dist+=V[i]*(T[i]-(V[i]-speed+V[i]-V[i+1]))
        dist+=V[i]*(V[i]-V[i+1])-0.5*(V[i]-V[i+1])**2
        speed=V[i]
      else:
        #print("23")

        if (speed>=V[i+1]):
          
          if (T[i]-(speed-V[i+1])>0):
            t=0.5*(T[i]-(speed-V[i+1]))
            dist+=speed*t+0.5*(t)**2
            dist+=(speed+t)*(T[i]-t)-0.5*(T[i]-t)**2
            speed=V[i+1]
            #print("HE")
          else:
            #print("XY")
            if (speed-V[i+1]-T[i]<=T[i-1]):
              t=speed-V[i+1]
              dist-=speed*(t-T[i])
              dist+=speed*t-0.5*(t)**2
            else: 
              t=speed-V[i+1]
              dist-=speed*(t-T[i])
              dist+=speed*t-0.5*(t)**2

        else:

          if (T[i]-(V[i+1]-speed)>0):
            #print("xt")
            t=0.5*(T[i]-(V[i+1]-speed))
            dist+=speed*(T[i]-t)+0.5*(T[i]-t)**2
            dist+=(speed+T[i]-t)*(t)-0.5*(t)**2
            speed=V[i+1]
          else:
            #print("XY")
            t=V[i+1]-speed
            dist-=speed*t
            dist+=speed*t-0.5*(t)**2


  else: 
    if (V[i]<=V[i+1]):
      dist+=V[i]*T[i]
      speed=V[i]
    else:
      dist+=V[i]*(T[i]-(V[i]-V[i+1]))
      dist+=V[i]*(V[i]-V[i+1])-0.5*(V[i]-V[i+1])**2
      speed=V[i+1]
  #print(dist)
print(dist)

Submission status: Wrong Answer

Solution code:
def solveDistance(t,v):
    ans = 0
    for i in range(1,len(t)):
        ans += (t[i]-t[i-1])*abs(v[i]-v[i-1])/2
        ans += (t[i]-t[i-1])*min(v[i],v[i-1])
    return ans

def getDistanceSegment(sStart, sEnd, length, sMax):
    tresult = [0]
    vresult = [sStart]

    decelPoint = (length + sEnd - sStart)/2
    decel = (length + sEnd + sStart)/2
 
    sMaxPoint = sMax - sStart
    decelFromMax = length - sMax + sEnd
    
    if sMaxPoint < decelPoint:
        tresult += [sMaxPoint]
        vresult += [sMax]
        if sEnd >= sMax:
            tresult += [length]
            vresult += [sMax]
        else:
            tresult += [decelFromMax, length]
            vresult += [sMax, sEnd]
    else:
        tresult += [decelPoint, length]
        vresult += [decel, sEnd]
    
    return solveDistance(tresult,vresult)
    
n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]

ans = 0
start=-1
end=-1
for i in range(n):
    if i == 0:
        start = 0
        if i == n-1:
            end = 0
        elif v[i+1] <= v[i]:
            end = v[i+1]
        else:
            end = v[0]
    elif i == n-1:
        start = v[-2]
        end = 0
    else:
        if v[i-1] < v[i]:
            start = v[i-1]
        else:
            start = v[i]
        if v[i+1] <= v[i]:
            end = v[i+1]
        else:
            end = v[i]

    ans+=getDistanceSegment(start,end,t[i],v[i])
print(ans)