SDRIVE - Lái xe
Tác giả: ladpro98
Ngôn ngữ: C++
#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); }
double getLengthCurve(int radius)
{ 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);
#ifdef _LAD_
freopen("SDRIVE.in", "r", stdin);
#endif // _LAD_
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;
}