## Editorial for Lái xe

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const double PI = 3.141592654;

int n, m, len[10010], type[10010];
double f[10010][22];

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> type[i];
for (int i = 1; i <= n; i++) cin >> len[i];

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = 1e18;
if (!type[i])
{
for (int jj = 1; jj <= m; jj++)
if (abs(j - jj) * 100 <= len[i])
f[i][j] = min(f[i][j], f[i - 1][jj] + sqrt(sqr(len[i]) + sqr((j - jj) * 10)));
}
else
{
double radius = len[i] + 5;
if (type[i] == 1) radius += 10 * (j - 1);
else radius += 10 * (m - j);
f[i][j] = f[i - 1][j] + radius * PI * 0.5;
}
}

double ans = 1e18;
for (int j = 1; j <= m; j++) ans = min(ans, f[n][j]);
printf("%.2lf\n", ans);
}


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 10005
#define M 25
#define sqr(x) ((x)*(x))

int l[N], n, m;
double f[N][M], s[N];

int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
freopen( "output.txt", "w", stdout );
#endif
scanf("%d%d",&n,&m);
fo(i,1,n) scanf("%d",l+i);
fo(i,1,n) scanf("%lf",s+i);
fo(i,1,n) fo(j,1,m) switch(l[i]){
case 2: f[i][j] = f[i-1][j] + (10*j-5+s[i])*M_PI/2; break;
case 1: f[i][j] = f[i-1][j] + (10*(m-j)+5+s[i])*M_PI/2; break;
default:
f[i][j] = DBL_MAX;
fo(k,max(1,j-(int)(s[i]/100)),min(m,j+(int)(s[i]/100)))
f[i][j] = min(f[i][j],f[i-1][k]+sqrt(sqr(s[i])+100*sqr(j-k)));
}
double res = DBL_MAX;
fo(i,1,m) res = min(res, f[n][i]);
printf("%.2lf\n", res);
return 0;
}


#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)

const double INF = 1e9;
const double PI = 3.141592654;
const int N = 10101;
const int M = 22;

using namespace std;

void minimize(double &a, double b)
{ a = a > b ? b : a; }

double getLengthLine(int a, int b)
{ return sqrt(a * a + b * b); }

{ return PI * radius / 2; }

int n, m;
int type[N], s[N];
double dp[2][M];

int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen("SDRIVE.in", "r", stdin);
cin >> n >> m;
REP(i, 1, n) cin >> type[i];
REP(i, 1, n) cin >> s[i];
int now = 0, nxt = 1;
REP(i, 1, n) {
REP(j, 1, m)
dp[nxt][j] = INF;
REP(j, 1, m) {
if (type[i] == 0) {
int range = s[i] / 100;
REP(k, max(1, j - range), min(m, j + range))
minimize(dp[nxt][k], dp[now][j] + getLengthLine(s[i], abs(j - k) * 10));
} else if (type[i] == 1) {
minimize(dp[nxt][j], dp[now][j] + getLengthCurve(s[i] + (j - 1) * 10 + 5));
} else {
minimize(dp[nxt][j], dp[now][j] + getLengthCurve(s[i] + (m - j) * 10 + 5));
}
}
now ^= 1; nxt ^= 1;
}
double ans = INF;
REP(i, 1, m)
minimize(ans, dp[now][i]);
cout << setprecision(2) << fixed << ans << endl;
return 0;
}


#### Code mẫu của RR

#include <iomanip>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i >= _b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
using namespace std;

long double f[10111][22];
int n, m;
int type[10111], s[10111];

#define sqr(x) ((x) * (x))

int main() {
cout << (fixed) << setprecision(10);
while (scanf("%d%d", &n, &m) == 2) {
FOR(i,1,n) scanf("%d", &type[i]);
FOR(i,1,n) scanf("%d", &s[i]);

FOR(i,1,n) FOR(j,1,m) f[i][j] = 1e50;
FOR(j,1,m) f[0][j] = 0;

FOR(i,0,n-1) FOR(j,1,m) {
if (type[i+1] == 0) {
FOR(jj,1,m)
if (abs(j - jj) * 100 <= s[i+1]) {
f[i+1][jj] = min(f[i+1][jj],
f[i][j] + sqrt(sqr((j - jj)*10.0) + sqr(s[i+1])));
}
}
else {
long double r = s[i+1];
if (type[i+1] == 1) r += (j - 0.5) * 10.0;
else r += (m - j + 0.5) * 10;

f[i+1][j] = min(f[i+1][j], f[i][j] + 3.141592654 * r / 2.0);
}
}
long double res = 1e50;
FOR(j,1,m) res = min(res, f[n][j]);

cout << res << endl;
}
return 0;
}


#### Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
//#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
if (rsz <= 0) {
ptr = 0;
rsz = (int) fread(bf, 1, bfsz, stdin);
if (rsz <= 0)
return EOF;
}
--rsz;
return bf[ptr++];
}
void ga(char &c) {
c = EOF;
while (!isalpha(c))
c = gc();
}
int gs(char s[]) {
int l = 0;
char c = gc();
while (isspace(c))
c = gc();
while (c != EOF && !isspace(c)) {
s[l++] = c;
c = gc();
}
s[l] = '\0';
return l;
}
template<class T> bool gi(T &v) {
v = 0;
char c = gc();
while (c != EOF && c != '-' && !isdigit(c))
c = gc();
if (c == EOF)
return false;
bool neg = c == '-';
if (neg)
c = gc();
while (isdigit(c)) {
v = v * 10 + c - '0';
c = gc();
}
if (neg)
v = -v;
return true;
}

typedef pair<int, int> II;

const ld PI = acos(-1.0);
const ld eps = 1e-9;

const int dr[] = {+1, +0, +0, -1};
const int dc[] = {+0, +1, -1, +0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
//const ll mod = (ll)1e9 + 7;

#define maxn 20005

int n, m, id[maxn];
ld f[maxn][22], d[maxn];

int main(){
//    freopen("in.txt", "r", stdin);
cin >> n >> m;
For(i, 1, n) cin >> id[i];
For(i, 1, n) cin >> d[i];

For(i, 1, n) For(j, 1, m) f[i][j] = linf;
For(i, 1, m) f[0][i] = 0;

For(i, 1, n){
if(id[i] == 2){
For(j, 1, m){
ld r = d[i] + 5.0 * (j + j - 1);
f[i][j] = f[i - 1][j] + r * PI / 2;
}
}
else if(id[i] == 1){
For(j, 1, m){
ld r = d[i] + 5.0 * (m + m - j - j + 1);
f[i][j] = f[i - 1][j] + r * PI / 2;
}
}
else{
int num = (int)((d[i] + 0.5) / 100);
For(j, 1, m){
For(k, max(1, j - num), min(m, j + num)){
ld r = 10.0 * abs(j - k);
ld dis = sqrt(r * r + d[i] * d[i]);
f[i][k] = min(f[i][k], f[i - 1][j] + dis);
}
}
}
}

ld res = linf;
For(i, 1, m) res = min(res, f[n][i]);
cout << fixed << setprecision(2) << res;
}


#### Code mẫu của skyvn97

#include<stdio.h>
#include<math.h>
#define PI   acos(-1.0)
#define INF   1e9
double f[10101][22];
int s[10101];
int l[10101];
int n,m;
void init(void) {
int i;
scanf("%d",&n);
scanf("%d",&m);
for (i=1;i<=n;i=i+1) scanf("%d",&l[i]);
for (i=1;i<=n;i=i+1) scanf("%d",&s[i]);
}
int abs(int x) {
if (x<0) return (-x); else return (x);
}
double min(double a,double b) {
if (a<b) return (a); else return (b);
}
void optimize(void) {
int i,j,k;
for (i=1;i<=m;i=i+1) f[0][i]=0;
for (i=1;i<=n;i=i+1)
for (j=1;j<=m;j=j+1) {
if (l[i]==0) {
f[i][j]=INF;
for (k=1;k<=m;k=k+1)
if (abs(j-k)*100<=s[i])
f[i][j]=min(f[i][j],f[i-1][k]+hypot((j-k)*10,s[i]));
}
if (l[i]==1) f[i][j]=f[i-1][j]+PI*(s[i]+j*10-5)/2;
if (l[i]==2) f[i][j]=f[i-1][j]+PI*(s[i]+5+10*m-10*j)/2;
}
double r=INF;
for (i=1;i<=m;i=i+1)
if (f[n][i]<r) r=f[n][i];
printf("%.2lf",r);
}
int main(void) {
init();
optimize();
}