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 = [int(i) for i in input().split()]
v = [int(i) for i in input().split()]
v_real = [v[i] for i in range(n) for j in range(t[i])]
v_real.append(0)
v_real.insert(0, 0)
def acc(v):
    for i in range(len(v)-1):
        if not -1 <= v[i+1] - v[i] and v[i+1] - v[i] <= 1:
            return False
    return True

def update(v):
    for i in range(len(v)-1):
        if v[i+1] - v[i] > 1:
            v[i+1] = v[i] + 1
        elif v[i+1] - v[i] < -1:
            v[i] = v[i+1] + 1
    return v

def calc(v):
    acc = []
    dis = 0
    for i in range(len(v)-1):
        if v[i+1] - v[i] == 1:
            acc.append(1)
        elif v[i+1] == v[i]:
            acc.append(0)
        else:
            acc.append(-1)
    for i in range(len(v)-1):
        dis += v[i] + 1./2 * acc[i]
    return dis
    
while not acc(v_real):
    v_real = update(v_real)
print (calc(v_real))

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 : 
            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:
# 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 : 
            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:
# 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(vs)
	#print(nod)
	ans = 0
	for i in range(len(ts)):
		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 - 1, 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:
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

print (border)
while t < time :
	t += 0.5

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

	for j in range(len(border)):
		
		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
	vlast = v0


print (ans)

Submission status: Wrong Answer

Solution code:
def solve(t1,v1,t2,v2,vmax):
  if v1 > vmax or v2 > vmax:
    return -inf
  vmax_theory = min(v1,v2)+((t2-t1)+abs(v2-v1))/2.0
  area1 = (vmax_theory-min(v1,v2))**2
  area2 = (abs(v1-v2))**2/2.0
  area3 = (t2-t1)*min(v1,v2) 
  if vmax_theory < vmax:
    return area1-area2+area3
  else: 
    area4 = (vmax_theory-vmax)**2
    return area1-area2+area3-area4

    
#print(solve(60,34,110,0,38))
#exit(0)

N = int(input())
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))
ts = [0] + ts
vs = [0] + vs

from itertools import accumulate
ts = list(accumulate(ts))

inf = 1000000007
dp = [[-inf for x in range(205)] for y in range(len(ts))]

t_idx = 0

t_tot = sum(ts)

for t_idx in range(len(ts)):
  if t_idx==0:
    dp[t_idx][0] = 0.0
  else:
    for v1 in range(vs[t_idx-1]+1):
      for v2 in range(vs[t_idx]+1):
#        if v1==34 and v2==0:
#          print(dp[t_idx-1][v1], vs[t_idx])
#          print(ts[t_idx-1],v1,ts[t_idx],v2,vs[t_idx])
#          print(solve(ts[t_idx-1], v1, ts[t_idx], v2, vs[t_idx]))
        dp[t_idx][v2] = max(dp[t_idx][v2],
                            dp[t_idx-1][v1] + solve(ts[t_idx-1], v1, ts[t_idx], v2, vs[t_idx])) 


#print(dp[1][34], dp[2][0])
print("{:.12f}".format(dp[len(ts)-1][0]))

Submission status: Wrong Answer

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

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
d_int = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	rest_t = [T[i]-now_t for i in range(N)]
	if now_v < v[now_n]:
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif now_v == v[now_n]: 
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 0
	for i in range(N):
		rest = rest_t[i]
		if rest > 0:
			d_v = now_v - v[i]
			if rest == d_v:
				a = -1

	d_int += 2 * int(now_v * 2) + a
	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d)

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
ts = map(int, raw_input().split())
vs = map(int, raw_input().split())

vs.append(0)

for i in xrange(N-1, -1, -1):
  vs[i] = min(vs[i], vs[i+1] + ts[i])

def dist(vstart, vend, time):
  return time * (min(vstart, vend) + (abs(vstart - vend) / 2.0))

v = 0
ans = 0.0
for i in xrange(N):
  a = min(ts[i], vs[i] - v)
  vs[i] = min(vs[i], vs[i] + a)
  b = max(0, vs[i] - vs[i+1]) # <= ts[i]
  c = ts[i] - a - b

  if c >= 0:
    ans += dist(v, vs[i], a) + dist(vs[i], vs[i], c) + dist(vs[i], vs[i+1], b)
  else:
    a, b = (a-b+ts[i])/2.0, (b-a+ts[i])/2.0
    ans += dist(v, v+a, a) + dist(v+a, v+a-b, b)

  v = v + a - b

print ans

Submission status: Wrong Answer

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

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
d_int = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	
	if now_v < v[now_n]:
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif now_v == v[now_n]: 
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 0

	d_int += 2 * int(now_v * 2) + a
	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d)

Submission status: Wrong Answer

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

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
d_int = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	
	a = 0
	if now_v < v[now_n]:
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif delta_t + delta_v == 0:
		a = -1

	d_int += 2 * int(now_v * 2) + a
	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d)

Submission status: Wrong Answer

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

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
d_int = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	
	a = 0
	if now_v < v[now_n]:
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif delta_t + delta_v == 0:
		a = -1

	d_int += 2 * int(now_v * 2) + a
	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d_int / 8)

Submission status: Wrong Answer

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

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	rest_t = total_t - now_t

	a = 0
	if rest_t == now_v:
		a = -1
	elif now_v < v[now_n]:
		if delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif delta_t + delta_v == 0:
		a = -1

	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d)

Submission status: Wrong Answer

Solution code:
N = input()
T = map(int, raw_input().split())
V = map(int, raw_input().split())

VL = [V[i] for i in xrange(N)]
for i in xrange(N-2, -1, -1):
    VL[i] = min(VL[i], VL[i+1] + T[i])
VL.append(0)

v1 = 0
v2 = 0
ans = 0

for i in xrange(N):
    t1 = 0
    v2 = v1

    hi = T[i] * 1.0
    lo = 0
    for _ in xrange(100):
        mid = (hi + lo) / 2
        tt = t1 + mid
        vv = v2 + mid
        if tt <= T[i] and vv <= V[i] and vv - (T[i] - tt) <= VL[i+1]:
            lo = mid
        else:
            hi = mid

    t1 += hi
    v2 = v1 + t1
    ans += (v1 + v2) / 2.0 * t1

    hi = (T[i] - t1) * 1.0
    lo = 0
    for _ in xrange(100):
        mid = (hi + lo) / 2
        tt = mid
        if t1 + tt <= T[i] and v2 - (T[i] - t1 - tt) < VL[i+1]:
            lo = mid
        else:
            hi = mid

    t2 = hi
    ans += v2 * t2

    v3 = v2 - (T[i] - t1 - t2)
    ans += (v2 + v3) / 2.0 * (T[i] - t1 - t2)

    v1 = v3

print "%.09f" % ans

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))+[0]
s,x=0,0
pf=[0]*(n+1)
for i in range(1,n+1):
	pf[i]=pf[i-1]+t[i-1]
for i in reversed(range(n)):
	for j in range(i+1,n+1):
		v[i]=min(v[i],v[j]+pf[j]-pf[i])
for i in range(n):
	if v[i+1]>v[i]:
		if v[i]-s>=t[i]:
			x+=(2*s+t[i])*t[i]/2
			s+=t[i]
		else:
			x+=(s+v[i])*(v[i]-s)/2+v[i]*(t[i]-v[i]+s)
			s=v[i]
	else:
		if t[i]-v[i]+s>=v[i]-v[i+1]:
			x+=(s+v[i])*(v[i]-s)/2+v[i]*(t[i]-2*v[i]+s+v[i+1])+(v[i]+v[i+1])*(v[i]-v[i+1])/2
		else:
			tt=(v[i+1]-s+t[i])/2
			x+=(2*s+tt)*tt/2+(v[i+1]+s+tt)*(t[i]-tt)/2
		s=v[i+1]
print(x)

Submission status: Wrong Answer

Solution code:
N = input()
t = map(int, raw_input().split())
v = map(int, raw_input().split())
v1 = [0]*N
v2 = [0]*N
for i in range(1,N):
    v1[i] = min(v1[i-1]+t[i-1], v[i-1], v[i])
for i in range(N-1)[::-1]:
    v2[i] = min(v2[i+1]+t[i+1], v[i+1], v[i])
ans = 0
for i in range(N):
    vm = min((v1[i]+v2[i]+t[i])*.5, v[i]*1.)
    ans += (vm-v1[i])**2*.5 + (vm-v1[i])*v1[i] + (vm-v2[i])**2*.5 + (vm-v2[i])*v2[i] + vm*(t[i]-(vm-v1[i])-(vm-v2[i]))
print "%.10f"%ans

Submission status: Wrong Answer

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

v.append(0)
interval = 0.5
total_t = sum(t)
now_t = 0
now_v = 0
T = [sum(t[:i]) for i in range(1,N+1)]
now_n = 0
d = 0
while now_t < total_t:
	nxt_t, nxt_v = T[now_n], v[now_n + 1]
	delta_t, delta_v = nxt_t - now_t, nxt_v - now_v
	rest_t = total_t - now_t

	a = 0
	if rest_t == now_v:
		a = -1
	elif now_v < v[now_n]:
		if now_v <= nxt_v:
			a = 1
		elif delta_t + delta_v == 0:
			a = -1
		else:
			a = 1
	elif delta_t + delta_v == 0:
		a = -1

	d += now_v * interval + 1/2 * a * interval * interval
	now_t += interval
	now_v += a * interval
	if now_t == T[now_n]:
		now_n += 1

print(d)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction as F

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

VL = [V[i] for i in xrange(N)]
for i in xrange(N-2, -1, -1):
    VL[i] = min(VL[i], VL[i+1] + T[i])
VL.append(0)

v1 = F(0)
v2 = F(0)
ans = F(0)

for i in xrange(N):
    t1 = F(0)
    v2 = F(v1)

    while t1 < T[i] and v2 < V[i] and v2 - (T[i] - t1) < VL[i+1]:
        t1 += F(1, 2)
        v2 += F(1, 2)
    v2 = v1 + t1
    ans += (v1 + v2) / F(2) * t1

    t2 = F(0)
    while t1 + t2 < T[i] and v2 - (T[i] - t1 - t2) < VL[i+1]:
        t2 += F(1, 2)
    ans += v2 * t2

    v3 = v2 - (T[i] - t1 - t2)
    ans += (v2 + v3) / F(2) * (T[i] - t1 - t2)

    v1 = v3

print "%.09f" % ans

Submission status: Wrong Answer

Solution code:
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))+[0]
s,x=0,0
for i in range(n):
	if v[i+1]>v[i]:
		if v[i]-s>=t[i]:
			x+=(2*s+t[i])*t[i]/2
			s+=t[i]
		else:
			x+=(s+v[i])*(v[i]-s)/2+v[i]*(t[i]-v[i]+s)
			s=v[i]
	else:
		if t[i]-v[i]+s>=v[i]-v[i+1]:
			x+=(s+v[i])*(v[i]-s)/2+v[i]*(t[i]-2*v[i]+s+v[i+1])+(v[i]+v[i+1])*(v[i]-v[i+1])/2
		else:
			tt=(v[i+1]-s+t[i])/2
			x+=(2*s+tt)*tt/2+(v[i+1]+s+tt)*(t[i]-tt)/2
		s=v[i+1]
print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())
ts = [int(c) for c in input().split()]
vs = [int(c) for c in input().split()]

t = sum(ts)
dp = [[-10 ** 10 for _ in range(101)] for _ in range(t + 1)]
dp[0][0] = 0.

mvs = []
for dt, mv in zip(ts, vs):
    for st in range(dt):
        mvs.append(mv)
mvs.append(0)

for ct in range(t):
    mv = mvs[ct]
    for cv in range(mv + 1):
        endmv = min(mv, mvs[ct+1])
        for dv in [-1, 0, 1]:
            nv = cv + dv
            if 0 <= nv <= endmv:
                dp[ct + 1][nv] = max(dp[ct][cv] + (cv + nv) / 2, dp[ct + 1][nv])
        if mv >= cv + 1 and cv >= endmv:
            dp[ct + 1][cv] = max(dp[ct+1][cv], dp[ct][cv] + cv + 0.25)


print(dp[t][0])

Submission status: Wrong Answer

Solution code:
n = int(input())
ts = [int(c) for c in input().split()]
vs = [int(c) for c in input().split()]

t = sum(ts)
dp = [[-10 ** 10 for _ in range(101)] for _ in range(t + 1)]
dp[0][0] = 0.

mvs = []
for dt, mv in zip(ts, vs):
    for st in range(dt):
        mvs.append(mv)
mvs.append(0)

for ct in range(t):
    mv = mvs[ct]
    for cv in range(mv + 1):
        endmv = min(mv, mvs[ct+1])
        for dv in [-1, 0, 1]:
            nv = cv + dv
            if 0 <= nv <= endmv:
                dp[ct + 1][nv] = max(dp[ct][cv] + (cv + nv) / 2, dp[ct + 1][nv])
        if endmv >= cv + 1:
            dp[ct + 1][cv] = max(dp[ct+1][cv], dp[ct][cv] + cv + 0.25)


print(dp[t][0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

## これで下記がちゃんとつくれた。
# Tleft[i] <= t <= Tright[i] の間、 V[i]以下でなければいけない

# VV[tt] tt/2秒時の速度。両端がゼロ、という条件から初期値を生成する。
VV = [min(i*0.5, (TMAX*2-i) * 0.5) for i in range(TMAX*2+1)]
#print(VV)

# 区間iについて
for i in range(N):
  for tt in range(TMAX*2+1):
    VV[tt] = min(VV[tt], V[i] + max(0, (T_Left[i]*2 - tt) * 0.5, (tt-T_Right[i]*2) * 0.5))
#print(VV)
# 面積は両端がゼロであることから、速度合計を２で割る（0.5秒ごとだから）で出る。
# v-tグラフの面積を台形の面積で考えればよい。
print(sum(VV)/2)

Submission status: Time Limit Exceeded

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

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
*t,=map(int,input().split())
tot=sum(t)
*v,=map(int,input().split())
lim1=[]
lim2=[(1,0,0),(-1,tot,tot)]
til=0
for t1,t2,v1 in zip([0]+t,t,v):
	lim1.append((til,til+t2,v1))
	lim2.append((-1,til,til+v1))
	lim2.append((1,til+t2,v1-(til+t2)))
	til+=t2
def mi(time):
	ret=float("inf")
	for l,r,lim in lim1:
		if l<=time<=r:
			ret=min(ret,lim)
	for f,tt,y in lim2:
		if f==-1 and time<=tt:
			ret=min(ret,y-time)
		if f==1 and time>=tt:
			ret=min(ret,time+y)
	return ret
print(sum(mi(i/2) for i in range(tot*2+1))/2)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**18

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
V = [0] + V + [0]
R = [(0, 0)]*(N+2)
for i in range(1,N+1):
    R[i] = (R[i-1][1], R[i-1][1] + T[i-1])
R[N+1] = (R[N][1], R[N][1])
def velocity(i, x):
    if x < R[i][0]:
        return V[i]+R[i][0]-x
    elif R[i][0] <= x <= R[i][1]:
        return V[i]
    else:
        return V[i]+x-R[i][1]
ans = 0
dp = [0]*(R[N+1][1]*2+1)
for x in range(1, R[N+1][1]*2+1):
    mi = INF
    for i in range(N+2):
        mi = min(velocity(i, x/2), mi)
    dp[x] = mi
    ans += 0.25*(dp[x-1]+mi)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(left, right, time, vmax):
    if left <= time and time <= right:
        return vmax
    elif time < left:
        return vmax + left - time
    else:
        return vmax + time - right

n = int(input())
t = list(map(int, input().split()))
v = list(map(int, input().split()))
tlst = [[0, t[0]]]
for i in range(1, n):
    start = tlst[-1][1]
    stop = start + t[i]
    tlst.append([start, stop])

tmax = sum(t)
vnow = 0
ans = 0
for i in range(1, 2*tmax+1):
    time = 0.5 * i
    vmin = 10**9
    for j in range(n):
        left, right = tlst[j][0], tlst[j][1]
        vmax = v[j]
        vmin = min(vmin, calc(left, right, time, vmax))
    vmin = min(vmin, calc(0, 0, time, 0))
    vmin = min(vmin, calc(tmax, tmax, time, 0))
    ans += 0.25 * (vmin + vnow)
    vnow = vmin
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

sdic={}
t=0
while(t<=tsum):
  s=10**9
  for con in const_list:
    l,r,v=con
    s=min(s,const(l,r,v,t))  
  sdic[t]=s
  t+=0.5

answer=0
t=0
while(t<tsum):
  answer+=(sdic[t]+sdic[t+0.5])*0.5/2
  t+=0.5
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  #print(s1,s2)
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)

Submission status: Time Limit Exceeded

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

dp = [[-1]*102 for _ in range(sum(T) + 1)]
dp[0][0] = 0

nt = 0
pt = T[0]
# i 秒から i+1 秒へ配る
delta = [-1,0,1]
for i in range(sum(T)):
    if pt == i:
        nt += 1
        pt += T[nt]
    for j in range(101):
        if j > V[nt] or dp[i][j] == -1:break
        for d in delta:
            nj = j + d
            if 0 <= nj <= V[nt]:
                if d != 0 or j == V[nt]:
                    dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + (j+nj)/2)
                else :
                    dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + j + 0.25)

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = list(map(int, input().split())) + [0]
v = list(map(int, input().split())) + [0]
m = sum(t)*2
g = [10**10]*(m+1)
l = [(0, 0, 0)]
for x, y in zip(t, v):
  l.append((l[-1][1], l[-1][1] + x*2, y))
for x, y, c in l:
  for i in range(m + 1):
    d = c
    if i < x:
      d += (x - i)*.5
    elif y < i:
      d += (i - y)*.5
    if g[i] > d:
      g[i] = d
print(sum(g)/2)

Submission status: Time Limit Exceeded

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

time = 0
sum_t = sum(t)
velo_cap =[float("inf")]*(2*sum_t+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum_t+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum_t+1):
  velo_cap[s] = min(velo_cap[s],2*sum_t-s,s)


print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
tTotal = sum(t)*2
speed = [min(i/2,(tTotal-i)/2) for i in range(tTotal+1)]
#?

start=0
end=0
#iter through segments
for i in range(n):
    end += t[i]*2
    for j in range(tTotal+1):
        speed[j] = min(speed[j], v[i] + max(0, -(j-start)/2, (j-end)/2))
    start = end

print(sum(speed)/2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()] + [0]
tTotal = sum(t)*2
speed = []
for i in range(tTotal+1):
    speed.append(min(i/2,(tTotal-i)/2))

start=0
end=0
#iter through segments
for i in range(n):
    end += t[i]*2
    for j in range(tTotal+1):
        speed[j] = min(speed[j], v[i] + max(0, -(j-start)/2, (j-end)/2))
    start = end

print(sum(speed)/2)

Submission status: Time Limit Exceeded

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

time=0
t=[0]
for i in T:
  time+=i
  t.append(time)
ans=0

for j in range(0,2*time):
  m1=1000000000
  m2=1000000000
  t1=j/2
  t2=(j+1)/2
  for i in range(N+2):
    if t1<=t[i]:
      m1=min(m1,V[i]+(t[i]-t1))
    elif t1<=t[i+1]:
      m1=min(m1,V[i])
    else:
      m1=min(m1,V[i]+t1-t[i+1])

    if t2<=t[i]:
      m2=min(m2,V[i]+(t[i]-t2))
    elif t2<=t[i+1]:
      m2=min(m2,V[i])
    else:
      m2=min(m2,V[i]+t2-t[i+1])
    
  #print(1,m1,m2)
  ans+=0.25*(m1+m2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n=int(input())
  arr1=list(map(int,input().split()))
  arr2=list(map(int,input().split()))
  m=min(arr2)
  tlist=[0]
  for val in arr1:
    tlist.append(tlist[-1]+val)
  t=tlist[-1]
  ans=0
  for i in range(1,2*t):
    tt=i/2
    if tt<=m or t-tt<=m:
      tmp=min(tt,t-tt)
    else:
      tmp=10**18
      for j in range(n):
        if tt<=tlist[j]:
          tmp=min(tmp,arr2[j]+(tlist[j]-tt))
        elif tlist[j+1]<=tt:
          tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
        else:
          tmp=min(tmp,arr2[j])
      tmp=min(tmp,tt)
      tmp=min(tmp,t-tt)
    ans+=tmp
  print(ans/2)
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n=int(input())
  arr1=list(map(int,input().split()))
  arr2=list(map(int,input().split()))
  tlist=[0]
  for val in arr1:
    tlist.append(tlist[-1]+val)
  t=tlist[-1]
  ans=0
  for i in range(1,2*t):
    tt=i/2
    tmp=10**18
    for j in range(n):
      if tt<=tlist[j]:
        tmp=min(tmp,arr2[j]+(tlist[j]-tt))
      elif tlist[j+1]<=tt:
        tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
      else:
        tmp=min(tmp,arr2[j])
    tmp=min(tmp,tt)
    tmp=min(tmp,t-tt)
    ans+=tmp
  print(ans/2)
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n=int(input())
  arr1=list(map(int,input().split()))
  arr2=list(map(int,input().split()))
  tlist=[0]
  for val in arr1:
    tlist.append(tlist[-1]+val)
  t=tlist[-1]
  ans=0
  vlist=[0]
  for i in range(1,2*t):
    tt=i/2
    tmp=10**18
    for j in range(n):
      if tt<=tlist[j]:
        tmp=min(tmp,arr2[j]+(tlist[j]-tt))
      elif tlist[j+1]<=tt:
        tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
      else:
        tmp=min(tmp,arr2[j])
    tmp=min(tmp,tt)
    tmp=min(tmp,t-tt)
    vlist.append(tmp)
  vlist.append(0)
  for i in range(len(vlist)-1):
    ans+=(vlist[i]+vlist[i+1])/4
  print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
tlist=[0]
for val in arr1:
  tlist.append(tlist[-1]+val)
t=tlist[-1]
ans=0
vlist=[0]
for i in range(1,2*t):
  tt=i/2
  tmp=10**18
  for j in range(n):
    if tt<=tlist[j]:
      tmp=min(tmp,arr2[j]+(tlist[j]-tt))
    elif tlist[j+1]<=tt:
      tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
    else:
      tmp=min(tmp,arr2[j])
  tmp=min(tmp,tt)
  tmp=min(tmp,t-tt)
  vlist.append(tmp)
vlist.append(0)
for i in range(len(vlist)-1):
  ans+=(vlist[i]+vlist[i+1])/4
print(ans)