解法
時刻と速度を軸としたグラフを書くと面積が距離となり， これを最大化する． 時刻 \(t\) と速度 \(v\) を状態とする DPができる． \(\ (t,v)\ \) が同じなら，次にできる遷移は同じになるため， そこに至るまでの道中を同一視できる．
簡単な問
速度制限無し ver. 丁度真ん中の時刻で折り返すと，答えが少数になることがある． 簡単のため，速度と時刻をそれぞれ2倍して考える． また，dp も遷移で三角形または台形の面積を使うので， 1/2 倍が出てしまう．そこで，dp の値も 2倍して保持することにして，
\( dp[t][v] = \) (2*距離)の最大値
とする．
今回の問
遷移に制限速度が付いた ver. 今の制限速度さえ求まれば遷移が書ける． 累積和を持ちながら \(t\) を動かせば， 今どの区間 \(i \in N\) にいるのかが分かる． それにより，制限速度 \(vs[i]\) も求まる． 制限速度が，時刻\(t\) までなのか，\(t+1\)までなのか，など 境界に気を付けて遷移する．
実装
面積を 8.0 で割って出力． 分母が 8までしか出ない計算なので， 最初から double で dp しても，おそらく AC出来る．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
vll vs(n),ts(n);
ll T = 0;
rep(i,n){
cin >> ts[i];
ts[i] *= 2;
T += ts[i];
}
ll V = 210; // V = T でも可能．
rep(i,n){
cin >> vs[i];
vs[i] *= 2;
}
ll cum_t = 0, ind = 0;
vll dp(V, -INFL);
dp[0] = 0;
rep(t,T){
vll old(V, -INFL);
swap(dp, old);
if(t >= cum_t){
cum_t += ts[ind];
ind++;
}
rep(v, V) if(v <= vs[ind-1]){
auto valid_v = [=](ll v) -> bool {
return in(v,vs[ind-1]+1);
};
ll ne = old[v] + 2*v;
chmax(dp[v], ne);
if(valid_v(v-1)) chmax(dp[v-1], ne - 1);
if(valid_v(v+1)) chmax(dp[v+1], ne + 1);
}
}
double ans = dp[0]/ 8.0;
printf("%.10lf\n", ans);
return 0;
}
