D - AtCoder Express


Time limit : 2sec / Memory limit : 256MB

Score :  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  seconds.
  • In the first  seconds, a train must run at a speed of at most  m/s (meters per second). Similarly, in the subsequent  seconds, a train must run at a speed of at most m/s, and so on.

According to the specifications of the trains, the acceleration of a train must be always within . 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

  • All input values are integers.

Input

Input is given from Standard Input in the following format:



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 .


Sample Input 1

Copy
1
100
30

Sample Output 1

Copy
2100.000000000000000

AtCoder Express(数学+二分)-LMLPHP

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

  • In the first  seconds, it accelerates at a rate of , covering  meters.
  • In the subsequent  seconds, it maintains the velocity of , covering  meters.
  • In the last  seconds, it decelerates at the acceleration of , covering  meters.

The total distance covered is  +  +  =  meters.


Sample Input 2

Copy
2
60 50
34 38

Sample Output 2

Copy
2632.000000000000000

AtCoder Express(数学+二分)-LMLPHP

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

  • In the first  seconds, it accelerates at a rate of , covering  meters.
  • In the subsequent  seconds, it maintains the velocity of , covering  meters.
  • In the subsequent  seconds, it accelerates at a rate of , covering  meters.
  • In the subsequent  seconds, it maintains the velocity of , covering  meters.
  • In the last  seconds, it decelerates at the acceleration of , covering  meters.

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


Sample Input 3

Copy
3
12 14 2
6 2 7

Sample Output 3

Copy
76.000000000000000

AtCoder Express(数学+二分)-LMLPHP

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

  • In the first  seconds, it accelerates at a rate of , covering  meters.
  • In the subsequent  seconds, it maintains the velocity of , covering  meters.
  • In the subsequent  seconds, it decelerates at the acceleration of , covering  meters.
  • In the subsequent  seconds, it maintains the velocity of , covering  meters.
  • In the last  seconds, it decelerates at the acceleration of , covering  meters.

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


Sample Input 4

Copy
1
9
10

Sample Output 4

Copy
20.250000000000000000

AtCoder Express(数学+二分)-LMLPHP

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

  • In the first  seconds, it accelerates at a rate of , covering  meters.
  • In the last  seconds, it decelerates at the acceleration of , covering  meters.

The total distance covered is  +  =  meters.


Sample Input 5

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

Sample Output 5

Copy
20291.000000000000

//题意:读了老半天,就是说一列火车在 n 段路上行驶,给出行驶的时间,和最大速度限制,起点终点速度要为 0 ,问最大可行驶的路程是多少?
//应该是头次做这种题吧, 所以,做的比较慢,先逆序扫一遍,可得到在每段路上行驶,为了到终点为 0 速度,限制速度是多少。
然后正序累加,具体操作是,二分(加速时间+匀速时间)的最大值,然后就可以轻松解决了
 # include <bits/stdc++.h>
using namespace std;
# define eps 1e-
# define INF 1e20
# define pi acos(-1.0)
# define MX
struct Node
{
double t,v;
double ev; //从终点的最大速度
}seg[MX]; int n;
double spd, ans; void gogo(int x)
{
double l=, r=seg[x].t;
double res = ;
while (l<r-eps) // <
{
double mid = (l+r)/;
if (mid + spd > seg[x].v-eps)
{
if ((seg[x].v - seg[x+].ev) + mid < seg[x].t+eps)
{
res = mid;
l = mid;
}
else r = mid;
}
else
{
if (mid + spd - (seg[x].t-mid) - seg[x+].ev < -eps) //<=
{
res = mid;
l = mid;
}
else r = mid;
}
} double jia, yun, jian;
if (spd + res < seg[x].v)
{
jia = res;
yun = ;
jian = seg[x].t - jia;
}
else
{
jia = seg[x].v - spd;
yun = res - jia;
jian = seg[x].t - jia - yun;
}
ans += 1.0/2.0*jia*jia + spd * jia;
ans += yun * seg[x].v; if (res+spd < seg[x].v)
{
ans += -1.0/2.0*jian*jian + (spd+jia) * jian;
spd = spd + jia - jian;
}
else
{
ans += -1.0/2.0*jian*jian + seg[x].v * jian;
spd = seg[x].v - jian;
} } int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%lf",&seg[i].t);
for (int i=;i<=n;i++)
scanf("%lf",&seg[i].v);
spd=0.0;
for (int i=n;i>=;i--)
{
if (spd+seg[i].t < seg[i].v+eps) //<=
spd += seg[i].t;
else
spd = seg[i].v;
seg[i].ev = spd;
}
ans = ;
spd = ;
seg[n+] = (Node){0.0, 0.0, 0.0}; for (int i=;i<=n;i++)
{
gogo(i);
}
printf("%.5f\n",ans);
return ;
}
05-17 21:06
查看更多