SDRIVE - Lái xe

Tác giả: happyboy99x

Ngôn ngữ: C++

#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;
}

Download