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:
from itertools import chain

double = lambda c: int(c)*2

N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):
  ndp = [0]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi_min = max(0,vf-t)
    vi_max = min(v_max,vf+t)
    for vi,d in enumerate(dp[vi_min:vi_max+1], start=vi_min):
      vp = (t+vi+vf)/2
      d += (2*vp*vp-vf*vf-vi*vi)
      if vp > v_max:
        d -= 2*(vp-v_max)**2
      ndp[vf] = max(ndp[vf],d)
  
  dp = ndp
 
print(dp[0]/8)

Submission status: Wrong Answer

Solution code:
from itertools import chain

N = int(input())
T = tuple(map(int,input().split()))
V = tuple(map(int,input().split()))

dp = [0]

for t,v_max in zip(T,V):

  ndp = [0]*(v_max+1)
  if len(dp) > v_max+1:
    dp = dp[:v_max+1]

  for vf in range(v_max+1):
    for vi,d in enumerate(dp):
      if abs(vf-vi) > t:
        continue
      vp = (t+vi+vf)/2
      d += (2*vp*vp-vf*vf-vi*vi)/2
      if vp > v_max:
        d -= (vp-v_max)**2
      ndp[vf] = max(ndp[vf],d)
  
  dp = ndp

print(dp[0])

Submission status: Wrong Answer

Solution code:
from itertools import chain

N = int(input())
T = tuple(map(int,input().split()))
V = tuple(map(int,input().split()))

dp = [0]

for t,v_max in zip(T,V):

  ndp = [0]*(v_max+1)
  if len(dp) > v_max+1:
    dp = dp[:v_max+1]

  for vf in range(v_max+1):
    vi_min = max(0,vf-t)
    vi_max = min(len(dp)-1,vf+t)
    for vi,d in enumerate(dp[vi_min:vi_max+1], start=vi_min):
      vp = (t+vi+vf)/2
      dd = (2*vp*vp-vf*vf-vi*vi)/2
      if vp > v_max:
        dd -= (vp-v_max)**2
      ndp[vf] = max(ndp[vf],d+dd)
  
  dp = ndp

print(dp[0])

Submission status: Wrong Answer

Solution code:
from itertools import chain

N = int(input())
T = tuple(map(int,input().split()))
V = tuple(map(int,input().split()))

dp = [0]

for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):

  ndp = [0]*(min(vf_max,v_max)+1)

  for vf in range(len(ndp)):
    vi_min = max(0,vf-t)
    vi_max = min(v_max,vf+t)
    for vi,d in enumerate(dp[vi_min:(vi_max+1)], start=vi_min):
      vp = (t+vi+vf)/2
      dd = (2*vp*vp-vf*vf-vi*vi)/2
      if vp > v_max:
        dd -= (vp-v_max)**2
      ndp[vf] = max(ndp[vf],d+dd)
  
  dp = ndp

print(dp[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
T = [int(x) for x in input().split(' ')]
V = [int(x) for x in input().split(' ')]
V.append(0)
s = sum(T)
time = [s]
for i in range(N):
    s -= T[N - 1 - i]
    time.append(s)
time.reverse()

s = 0
answer = 0.0
for i in range(N):
    t = T[i]
    limit = V[i]
    g = V[i + 1]
    for j in range(i + 2, N + 1):
        if V[j] + time[j] - time[i + 1] < g:
            g = V[j] + time[j] - time[i + 1]
    x = (s + g + t) / 2
    if t <= limit - s and g >= limit:
        answer += 0.5 * t * (2 * s + t)
        s += t
    elif t > limit - s and g >= limit:
        answer += 0.5 * (limit ** 2 - s ** 2) + limit * (t - limit + s)
        s = limit
    elif x >= limit and s - g <= t:
        answer += limit ** 2 - 0.5 * (s ** 2 + g ** 2) + limit * (t - 2 * limit + s + g)
        s = g
    elif x < limit and s - g <= t:
        answer += x ** 2 - 0.5 * (s ** 2 + g ** 2)
        s = g
    elif s - g == t:
        answer += 0.5 * (s + g) * t
        s = g
    else:
        print("error")
        break

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
T = [int(x) for x in input().split(' ')]
V = [int(x) for x in input().split(' ')]
V.append(0)
s = sum(T)
time = [s]
for i in range(N):
    s -= T[N - 1 - i]
    time.append(s)
time.reverse()

s = 0
answer = 0.0
for i in range(N):
    t = T[i]
    limit = V[i]
    g = V[i + 1]
    for j in range(i + 2, N + 1):
        if V[j] + time[j] - time[i + 1] < g:
            g = V[j] + time[j] - time[i + 1]
    x = (s + g + t) / 2
    if t <= limit - s and g >= limit:
        answer += 0.5 * t * (2 * s + t)
        s += t
    elif t >= limit - s and g >= limit:
        answer += 0.5 * (limit ** 2 - s ** 2) + limit * (t - limit + s)
        s = limit
    elif x >= limit and s - g <= t:
        answer += limit ** 2 - 0.5 * (s ** 2 + g ** 2) + limit * (t - 2 * limit + s + g)
        s = g
    elif x < limit and s - g <= t:
        answer += x ** 2 - 0.5 * (s ** 2 + g ** 2)
        s = g
    elif s - g == t:
        answer += 0.5 * (s + g) * t
        s = g
    else:
        print("error")
        break

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
T = [int(x) for x in input().split(' ')]
V = [int(x) for x in input().split(' ')]
V.append(0)
s = sum(T)
time = [s]
for i in range(N):
    s -= T[N - 1 - i]
    time.append(s)
time.reverse()

s = 0
answer = 0
for i in range(N):
    t = T[i]
    limit = V[i]
    g = V[i + 1]
    for j in range(i + 2, N + 1):
        if V[j] + time[j] - time[i + 1] < g:
            g = V[j] + time[j] - time[i + 1]
    x = (s + g + t) / 2
    if t <= limit - s and g >= limit:
        answer += 0.5 * t * (2 * s + t)
        s += t
    elif t >= limit - s and g >= limit:
        answer += 0.5 * (limit ** 2 - s ** 2) + limit * (t - limit + s)
        s = limit
    elif x >= limit and s - g <= t:
        answer += limit ** 2 - 0.5 * (s ** 2 + g ** 2) + limit * (t - 2 * limit + s + g)
        s = g
    elif x < limit and s - g <= t:
        answer += x ** 2 - 0.5 * (s ** 2 + g ** 2)
        s = g
    elif s - g == t:
        answer += 0.5 * (s + g) * t
        s = g
    else:
        print(q)
        
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

N = int(input())
T = [int(x) for x in input().split(' ')]
V = [int(x) for x in input().split(' ')]
V.append(0)
s = sum(T)
time = [s]
for i in range(N):
    s -= T[N - 1 - i]
    time.append(s)
time.reverse()

s = 0
answer = 0
for i in range(N):
    t = T[i]
    limit = V[i]
    g = V[i + 1]
    for j in range(i + 2, N + 1):
        if V[j] + time[j] - time[i + 1] < g:
            g = V[j] + time[j] - time[i + 1]
    x = (s + g + t) / 2
    if t <= limit - s and g >= limit:
        answer += 0.5 * t * (2 * s + t)
        s += t
    elif t >= limit - s and g >= limit:
        answer += 0.5 * (limit ** 2 - s ** 2) + limit * (t - limit + s)
        s = limit
    elif x >= limit and s - g <= t:
        answer += limit ** 2 - 0.5 * (s ** 2 + g ** 2) + limit * (t - 2 * limit + s + g)
        s = g
    elif x < limit and s - g <= t:
        answer += x ** 2 - 0.5 * (s ** 2 + g ** 2)
        s = g
    elif s - g == t:
        answer += 0.5 * (s + g) * t
        s = g
    else:
        print("error")
        sys.exit(-1)
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
T = [int(x) for x in input().split(' ')]
V = [int(x) for x in input().split(' ')]
V.append(0)
s = sum(T)
time = [s]
for i in range(N):
    s -= T[N - 1 - i]
    time.append(s)
time.reverse()

s = 0
answer = 0
for i in range(N):
    t = T[i]
    limit = V[i]
    g = V[i + 1]
    for j in range(i + 2, N + 1):
        if V[j] + time[j] - time[i + 1] < g:
            g = V[j] + time[j] - time[i + 1]
    x = (s + g + t) / 2
    if t <= limit - s and g >= limit:
        answer += 0.5 * t * (2 * s + t)
        s += t
    elif t >= limit - s and g >= limit:
        answer += 0.5 * (limit ** 2 - s ** 2) + limit * (t - limit + s)
        s = limit
    elif x >= limit and s - g <= t:
        answer += limit ** 2 - 0.5 * (s ** 2 + g ** 2) + limit * (t - 2 * limit + s + g)
        s = g
    elif x < limit and s - g <= t:
        answer += x ** 2 - 0.5 * (s ** 2 + g ** 2)
        s = g
    elif s - g == t:
        answer += 0.5 * (s + g) * t
        s = g
    else:
        print("error")
        break
print(answer)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
time=list(map(int,input().split()))
timetable=list(itertools.accumulate([0]+time))
v_max=list(map(int,input().split()))
dt=0.5
v_table=[i*0.5 if i<sum(time) else (sum(time)*2-i)*0.5 for i in range(sum(time)*2)]
for i in range(n):
    t_s,t_e=timetable[i],timetable[i+1]
    for j in range(len(v_table)):
        if j*dt<t_s:
            v=v_max[i]+(t_s-j*dt)
        elif t_s<=j*dt<=t_e:
            v=v_max[i]
        else:
            v=v_max[i]+(j*dt-t_e)
        v_table[j]=min(v_table[j],v)
print(int(sum(v_table)*dt))

Submission status: Wrong Answer

Solution code:
#! usr/bin/env python3

#D:Atcoder Express

N = int(input())

gragh = [0]

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

for i in range(1,N):
	t[i] += t[i-1]
t.insert(0,0)

sumt = t[-1]


for i in range(1,sumt*2+1):
	gragh.append(0.5*i)


a = gragh[:]

for j in range(N):
	for i in range(1,sumt*2+1):
		if t[j]*2 > i:
			tmp = (t[j]+v[j]-0.5*i)
			if gragh[i] > tmp:
				gragh[i] = tmp
		elif t[j]*2 <= i < (t[j+1]*2) :
			if gragh[i] > v[j]:
				gragh[i] = float(v[j])
		else:
			tmp = (v[j]+0.5*(i-t[j+1]*2+1))
			if gragh[i] > tmp:
				gragh[i] = tmp

a.reverse()
for i in range(sumt*2+1):
	if  gragh[i] > a[i] :
		gragh[i] = a[i]


val = 0
for i in range(sumt*2):
	if gragh[i] != gragh[i+1]:
		val += ((gragh[i]+gragh[i+1]) * 0.25)
	else:
		val += ((gragh[i]) * 0.5 )

print(val)

Submission status: Wrong Answer

Solution code:
n = int(input())

tt = list(map(int, input().split()))
v = list(map(int, input().split()))

time = sum(tt);

border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
	temp += tt[i]
	border[i+1] = temp
	start_v[i] = v[i]
	end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0

# print (border)
while t < time :
	t += 0.5
	
	# tle回避
	if t < border[idx+1] and abs(v0- (vlast-0.5) ) < 0.001:
		v0 = vlast - 0.5
		ans += 0.5 * (vlast + v0) / 2
		vlast = v0
		continue

	vlast = v0

	#直接制約
	v0 = v[idx]
	if t == border[idx+1]:
		idx += 1
#		v0 = min(v0, v[idx])

	for j in range(n+1):
		
		if border[j] <= t:
			#前の時刻からの制約
			temp = end_v[j] + (t - border[j])
			if v0 > temp:
				v0 = temp
		if border[j] >= t:
			#後ろの時刻からの制約
			temp = start_v[j] + (border[j] - t)
			if v0 > temp:
				v0 = temp

#	print(v0)

	# ans += 0.5 * (vlast + v0) / 2
	ans += 0.5 * (vlast + v0) / 2
# 	vlast = v0

print (ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(n)]
S1=[0 for i in range(n)]
S2=[0 for i in range(n)]
vel=[0 for i in range(n)]

dt=[0 for i in range(n)]
v0=[0 for i in range(n)]
ve=[0 for i in range(n)]
ok=0



for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        ve[i]=min(v[i+1],v[i])
        dt[i]=t[i]

while ok==0:
    for i in range(n-1):
        if  abs((ve[i]-ve[i+1])/dt[i+1]) >1:
            ve[i]=ve[i]-1
            v0[i+1]=v0[i+1]-1
    else:
        ok=1





for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=(ttt-v[i]+v0[i])*(vvv-v[i]) 
    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=0

print(sum(S))

Submission status: Wrong Answer

Solution code:
n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(n)]
S1=[0 for i in range(n)]
S2=[0 for i in range(n)]
vel=[0 for i in range(n)]

dt=[0 for i in range(n)]
v0=[0 for i in range(n)]
ve=[0 for i in range(n)]
ok=0



for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        ve[i]=min(v[i+1],v[i])
        dt[i]=t[i]

while ok==0:
    for i in range(n-1):
        if  abs((ve[i]-ve[i+1])/dt[i]) >1:
            ve[i]=ve[i]-1
            v0[i+1]=v0[i+1]-1
    else:
        ok=1





for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=(ttt-v[i]+v0[i])*(vvv-v[i]) 
    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=0

print(sum(S))

Submission status: Wrong Answer

Solution code:
n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(n)]
S1=[0 for i in range(n)]
S2=[0 for i in range(n)]
vel=[0 for i in range(n)]

dt=[0 for i in range(n)]
v0=[0 for i in range(n)]
ve=[0 for i in range(n)]

for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        ve[i]=min(v[i+1],v[i])
        dt[i]=t[i]
"""
print(dt)
print(v0)
print(ve)
print(v)
"""

for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=(ttt-v[i]+v0[i])*(vvv-v[i]) 
    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=0

print(sum(S))

Submission status: Wrong Answer

Solution code:
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
vs.append(0)

ss = [ts[0]]
for i in range(1, n):
    ss.append(ss[-1])
    ss[-1] += ts[i]

ds = [[-1 for _ in range(101)] for _ in range(2)]
ds[0][0] = 0
i = 0
for t in range(1, ss[-1] + 1):
    vl = vs[i]
    ve = vs[i]
    if t == ss[i]:
        i += 1
        ve = min(ve, vs[i])
    for v in range(100):
        ds[t % 2][v] = -1
        if 0 <= ds[(t - 1) % 2][v]:
            if v < vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + 4 * v + 1
            elif v == vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + 4 * v
    for v in range(1, 101):
        if 0 <= ds[(t - 1) % 2][v] and v <= vl and v - 1 <= ve:
            ds[t % 2][v - 1] = max(ds[t % 2][v - 1], ds[(t - 1) % 2][v] + 4 * v - 2)
    for v in range(99):
        if 0 <= ds[(t - 1) % 2][v] and v < vl and v + 1 <= ve:
            ds[t % 2][v + 1] = max(ds[t % 2][v + 1], ds[(t - 1) % 2][v] + 4 * v + 2)

print(ds[ss[-1] % 2][0] / 4)

Submission status: Wrong Answer

Solution code:
EPS = 1E-6
n = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))
vs.append(0)

ss = [ts[0]]
for i in range(1, n):
    ss.append(ss[-1])
    ss[-1] += ts[i]

ds = [[-1.0 for _ in range(101)] for _ in range(2)]
ds[0][0] = 0.0
i = 0
for t in range(1, ss[-1] + 1):
    vl = vs[i]
    ve = vs[i]
    if t == ss[i]:
        i += 1
        ve = min(ve, vs[i])
    for v in range(100):
        ds[t % 2][v] = -1.0
        if -EPS <= ds[(t - 1) % 2][v]:
            if v < vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + v + 0.25
            elif v == vl and v <= ve:
                ds[t % 2][v] = ds[(t - 1) % 2][v] + v
    for v in range(1, 101):
        if -EPS <= ds[(t - 1) % 2][v] and v <= vl and v - 1 <= ve:
            ds[t % 2][v - 1] = max(ds[t % 2][v - 1], ds[(t - 1) % 2][v] + v - 0.5)
    for v in range(99):
        if -EPS <= ds[(t - 1) % 2][v] and v < vl and v + 1 <= ve:
            ds[t % 2][v + 1] = max(ds[t % 2][v + 1], ds[(t - 1) % 2][v] + v + 0.5)

print(ds[ss[-1] % 2][0])

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))

    ct = 0  # cumulative time
    M = [float('inf') for x in range(len(T))]  # ct,max speed
    CT = [0 for x in range(len(T))]  # ct,max speed

    count = 0
    for t, v in zip(T, V):
        CT[count] = ct
        ct += t
        count += 1

    for n in range(len(V)):
        if n == 0:
            continue
        for i in range(n):
            M[i] = min(M[i], V[n] + (CT[n] - CT[i]))
    M[len(T)-1] = T[N-1]

    now = 0
    S = 0
    for q in range(len(T)):
        future = M[q]
        restriction = V[q]
        for s in range(T[q]*2):
            future -= 0.5
            pnow = now
            now = min(min(future, restriction), now + 0.5)
            S += (now + pnow)/4
            # print(q, s, now, S, future)

    print(S)

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

    ct = 0  # cumulative time
    M = [float('inf') for x in range(len(T))]  # ct,max speed
    CT = [0 for x in range(len(T))]  # ct,max speed

    count = 0
    for t, v in zip(T, V):
        CT[count] = ct
        ct += t
        count += 1

    for n in range(len(V)):
        if n == 0:
            continue
        for i in range(n):
            M[i] = min(M[i], V[n] + (CT[n] - CT[i]))
    M[len(T)-1] = T[N-1]

    now = 0
    S = 0
    for q in range(len(T)):
        future = M[q]
        restriction = V[q]
        for s in range(T[q]):
            future -= 1
            pnow = now
            now = min(min(future, restriction), now + 1)
            S += (now + pnow)/2
            # print(q, s, now, S, future)

    print(S)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
num = int(input())
in1 = input().split(" ")
in2 = input().split(" ")
times = [0]
ct = 0
for a in range(num):
    in1[a] = int(in1[a])
    in2[a] = int(in2[a])
for a in range(num):
    ct += in1[a]
    times.append(ct)
vlimit = []
for a in range(1,num):
    vlimit.append(min(in2[a-1],in2[a]))
vlimit.append(in2[num-1])
print(in1,in2)
print(times,vlimit)

bairitu = 300

last = times[len(times)-1]
limit = [0 for a in range(last*bairitu+1)]

for a in range(last*bairitu):
    limit[a] = round(min(a / bairitu, last - a / bairitu),2)
for a in range(len(vlimit)):
    start = times[a] * bairitu
    end = times[a+1] * bairitu
    for b in range(start,end):
        limit[b] = min(limit[b],in2[a])
# print(str(limit))

for a in range(len(vlimit)):
    for b in range(0,times[a+1]*bairitu):
        limit[b] = min(limit[b],times[a+1] - b / bairitu + vlimit[a])
    for b in range(times[a+1]*bairitu+1,last*bairitu+1):
        limit[b] = min(limit[b],b / bairitu - times[a+1] + vlimit[a])

ans = 0
for a in range(1,len(limit)):
    ans += (limit[a] + limit[a-1])/ bairitu / 2
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np
import copy as cp

N = int(input())
T = input().split()
V = input().split()
T = [int(i) for i in T]
V = [int(i) for i in V]
sumOfT = sum(T)

v = 0
L = 0
t = 0
for i in range(N) : 
    #区間iでは T[i]秒間　最大速度V[i]を出すことができます
    if i == (N - 1) : nextV = 0
    else : nextV = V[i + 1]
    for j in range(T[i]*2):
        nowv = v
        t += 1/2
        leftTime = T[i] - j/2
        diffOfV = v - nextV
        if leftTime  <= diffOfV : 
            v -= 0.5
        elif v < V[i] :
            v += 0.5
        L += (v+nowv)/4
    
print(L)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy

def main():
	n = int(input())
	ts = list(map(int, input().split()))
	vs = list(map(int, input().split()))

	nod = copy.deepcopy(vs)
	nod = calcMaxMin(n, ts, nod)
	#print(nod)
	ans = 0
	for i in range(len(ts)):
		#print(calcDis(nod[i], nod[i+1], ts[i], vs[i]))
		ans += calcDis(nod[i], nod[i+1], ts[i], vs[i])
	print(ans)

def calcDis(b0, b1, t, v):
	cr1 = v - b0
	cr2 = - v + b1 + t
	cr3 = (b1 - b0 + t) / 2

	if 0 <= cr1 <= t:
		return (b0 + v) * cr1 / 2  + v * (cr2 - cr1) + (b1 + v) * (t - cr2) / 2
	else:
		return (b0 + (b0 + cr3)) * cr3 / 2 +  (b1 + (b0 + cr3)) * (t - cr3) / 2

def calcMaxMin(n, ts, vs):
	vs.insert(0, 0)
	vs.append(0)
	nod = [min(vs[i], vs[i + 1]) for i in range(len(vs) - 1)]
	for i in range(len(nod)):
		#print(i)
		nod =  modMaxMin(ts, nod, i)

	return nod


def modMaxMin(ts, nod, i):
	#forward
	for i2 in range(i, len(ts) - 1):
		nod[i2 + 1] = min(nod[i2 + 1], nod[i2] + ts[i2])

	#backward
	for i2 in range(i, 0, -1):
		nod[i2 - 1] = min(nod[i2 - 1], nod[i2] + ts[i2 - 1])

	return nod


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy

def main():
	n = int(input())
	ts = list(map(int, input().split()))
	vs = list(map(int, input().split()))

	nod = copy.deepcopy(vs)
	nod = calcMaxMin(n, ts, nod)
	print(nod)
	ans = 0
	for i in range(len(ts)):
		print(calcDis(nod[i], nod[i+1], ts[i], vs[i]))
		ans += calcDis(nod[i], nod[i+1], ts[i], vs[i])
	print(ans)

def calcDis(b0, b1, t, v):
	cr1 = v - b0
	cr2 = - v + b1 + t
	cr3 = (b1 - b0 + t) / 2

	if 0 <= cr1 <= t:
		return (b0 + v) * cr1 / 2  + v * (cr2 - cr1) + (b1 + v) * (t - cr2) / 2
	else:
		return (b0 + (b0 + cr3)) * cr3 / 2 +  (b1 + (b0 + cr3)) * (t - cr3) / 2

def calcMaxMin(n, ts, vs):
	vs.insert(0, 0)
	vs.append(0)
	nod = [min(vs[i], vs[i + 1]) for i in range(len(vs) - 1)]
	for i in range(len(nod)):
		#print(i)
		nod =  modMaxMin(ts, nod, i)

	return nod


def modMaxMin(ts, nod, i):
	#forward
	for i2 in range(i, len(ts) - 1):
		nod[i2 + 1] = min(nod[i2 + 1], nod[i2] + ts[i2])

	#backward
	for i2 in range(i, 0, -1):
		nod[i2 - 1] = min(nod[i2 - 1], nod[i2] + ts[i2 - 1])

	return nod


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np
import copy as cp

N = int(input())
T = input().split()
V = input().split()
T = [int(i) for i in T]
V = [int(i) for i in V]
sumOfT = sum(T)

v = 0
L = 0
t = 0
for i in range(N) : 
    #区間iでは T[i]秒間　最大速度V[i]を出すことができます
    if i == (N - 1) : nextV = 0
    else : nextV = V[i + 1]
    for j in range(T[i]):
        t += 1
        leftTime = T[i] - j
        diffOfV = v - nextV
        if leftTime  <= diffOfV : 
            if leftTime - 1  <= diffOfV : L += v + 1/4
            v -= 1
            L += v + 1/2
        elif v < V[i] :
            if leftTime - 1  <= diffOfV : L += v + 1/4
            else : 
                #加速します
                v += 1
                L += v - 1/2
        else : 
            L += v
print(L)

Submission status: Wrong Answer

Solution code:
import sys

def dump(v):
    for i in range(len(v)):
        sys.stdout.write(str(v[i])+" ")
    sys.stdout.write("\n")

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

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

vel=[0]*(hort+1)

capacity = v[0]
k=0
for i in range(hort):
    #dump(vel)
    if i+1 >= t[k]:
        k+=1
    if k < len(v):
        capacity = v[k]
    if i == hort-1:
        capacity=0
    if vel[i] < capacity:
        vel[i+1]=vel[i]+1
    elif vel[i] == capacity:
        vel[i+1]=vel[i]
    elif vel[i] > capacity:
        for j in range(i):
            if j == 0:
                vel[i+1]=capacity
            elif abs(vel[i-j+1] - vel[i-j+2])<=1:
                break
            else:
                vel[i+1-j] = vel[i+2-j]+1
            
velodd = [0]*(hort+1)
k=0
capacity = v[0]
oddbl = False
if hort %2 == 1:
    for i in range(hort//2+1):
        velodd[i] = i
    for i in range(hort//2+1):
        velodd[hort-i] = i
    for i in range(hort):
        if i >= t[k]:
            k+=1
        capacity = v[k]
        if velodd[i] > capacity or (i == (hort//2) and velodd[i] == capacity):
            break
        if i == hort-1:
            oddbl = True

#dump(vel)
            
dis2=0
for i in range(hort):
    dis2+=vel[i]+vel[i+1]
    
if oddbl:
    print(hort*hort/4)
else:
    print(dis2/2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys, re, copy, math, itertools
from copy import *
from collections import deque, defaultdict
from heapq import *
from bisect import *
import numpy as np
#import scipy as sp

# 止まれないので間違ってるが, とりあえず全速力

# 読み込み
N = int( input() )
t = list( map(int, input().split() ) )
v = list( map(int, input().split() ) )

# 時間合計
T = sum(t)

# 速度
v2 = np.zeros(T+1, np.float64)

# 区間ごとの最大速度・限界速度・加速度考慮した限界速度 の最小値
t_ = 0
for i in range( len(t) ):
    for j in range(t_, t_ + t[i] + 1):
        if i>=1: v2[j] = v[i-1] + j
        else:    v2[j] = j
        v2[j] = min( v2[j], v[i] )
        
        if i<N-1: v2[j] = min( v2[j], v[i+1] + t[i] - j )
        else    : v2[j] = min( v2[j], 0 + t[i] - j )
        
        v2[j] = max( v2[j], 0 )
    
    t_ += t[i]

# 速度を積分
#print(v2)
print( sum(v2) )

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    T = list(map(int, input().split()))
    V = list(map(int, input().split()))
    print(V)

    ct = 0  # cumulative time
    M = [float('inf') for x in range(len(T))]  # ct,max speed
    CT = [0 for x in range(len(T))]  # ct,max speed

    count = 0
    for t, v in zip(T, V):
        CT[count] = ct
        ct += t
        count +=1
        print(t,v)

    print(CT)

    for n in range(len(T)):
        if n == 0:
            continue
        for i in range(n):
            M[i] = min(M[i], V[n] + (CT[n] - CT[i]))

    total = CT[-1] + T[-1]
    now = 0
    S = 0
    for q in range(len(T)):
        future = M[q]
        restriction = V[q]
        for s in range(T[q]):
            if s == 0:
                continue
            future -= 1
            pnow = now
            now = max(min(future, restriction), now + 1)
            S += (now + pnow)/2

    print(S)

if __name__ == "__main__":
    main(
            )

Submission status: Wrong Answer

Solution code:
import sys

def dump(v):
    for i in range(len(v)):
        sys.stdout.write(str(v[i])+" ")
    sys.stdout.write("\n")

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

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

vel=[0]*(hort+1)

capacity = v[0]
k=0
for i in range(hort):
    dump(vel)
    if i+1 >= t[k]:
        k+=1
    if k < len(v):
        capacity = v[k]
    if i == hort-1:
        capacity=0
    if vel[i] < capacity:
        vel[i+1]=vel[i]+1
    elif vel[i] == capacity:
        vel[i+1]=vel[i]
    elif vel[i] > capacity:
        for j in range(i):
            if j == 0:
                vel[i+1]=capacity
            elif abs(vel[i-j+1] - vel[i-j+2])<=1:
                break
            else:
                vel[i+1-j] = vel[i+2-j]+1
            
velodd = [0]*(hort+1)
k=0
capacity = v[0]
oddbl = False
if hort %2 == 1:
    for i in range(hort//2+1):
        velodd[i] = i
    for i in range(hort//2+1):
        velodd[hort-i] = i
    for i in range(hort):
        if i >= t[k]:
            k+=1
        capacity = v[k]
        if velodd[i] > capacity or (i == (hort//2) and velodd[i] == capacity):
            break
        if i == hort-1:
            oddbl = True

dump(vel)
            
dis2=0
for i in range(hort):
    dis2+=vel[i]+vel[i+1]
    
if oddbl:
    print(hort*hort/4)
else:
    print(dis2/2)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = [0] + list(map(int, input().split()))
v = list(map(int, input().split())) + [0]

result = t[1] * (t[1] / 2) / 2
if v[0] < t[1] / 2:
    result -= ((t[1] - v[0]) - v[0]) * (t[1] / 2 - v[0]) / 2

print(result)