2034908d41 2012-05-20        kinaba: #include <iostream>
2034908d41 2012-05-20        kinaba: #include <sstream>
2034908d41 2012-05-20        kinaba: #include <iomanip>
2034908d41 2012-05-20        kinaba: #include <vector>
2034908d41 2012-05-20        kinaba: #include <string>
2034908d41 2012-05-20        kinaba: #include <map>
2034908d41 2012-05-20        kinaba: #include <set>
2034908d41 2012-05-20        kinaba: #include <algorithm>
2034908d41 2012-05-20        kinaba: #include <numeric>
2034908d41 2012-05-20        kinaba: #include <iterator>
2034908d41 2012-05-20        kinaba: #include <functional>
2034908d41 2012-05-20        kinaba: #include <complex>
2034908d41 2012-05-20        kinaba: #include <queue>
2034908d41 2012-05-20        kinaba: #include <stack>
2034908d41 2012-05-20        kinaba: #include <cmath>
2034908d41 2012-05-20        kinaba: #include <cassert>
2034908d41 2012-05-20        kinaba: using namespace std;
2034908d41 2012-05-20        kinaba: typedef long long LL;
2034908d41 2012-05-20        kinaba: typedef long double LD;
2034908d41 2012-05-20        kinaba: typedef complex<LD> CMP;
2034908d41 2012-05-20        kinaba: 
2034908d41 2012-05-20        kinaba: template<typename T>
2034908d41 2012-05-20        kinaba: struct DP2x
2034908d41 2012-05-20        kinaba: {
2034908d41 2012-05-20        kinaba: 	const int N1, N2;
2034908d41 2012-05-20        kinaba: 	vector<T> data;
2034908d41 2012-05-20        kinaba: 	DP2x(int, int N2, const T& t = T())
2034908d41 2012-05-20        kinaba: 		: N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
2034908d41 2012-05-20        kinaba: 	T& operator()(int i1, int i2)
2034908d41 2012-05-20        kinaba: 		{ i1&=1; return data[ (i1*N2)+i2 ]; }
2034908d41 2012-05-20        kinaba: 	void swap(DP2x& rhs)
2034908d41 2012-05-20        kinaba: 		{ data.swap(rhs.data); }
2034908d41 2012-05-20        kinaba: };
2034908d41 2012-05-20        kinaba: 
2034908d41 2012-05-20        kinaba: class EllysRivers { public:
2034908d41 2012-05-20        kinaba: 	double getMin(int length, int walk, vector <int> width, vector <int> speed)
2034908d41 2012-05-20        kinaba: 	{
2034908d41 2012-05-20        kinaba: 		DP2x<LD> dp(width.size()+1, length+1);
2034908d41 2012-05-20        kinaba: 		for(int x=0; x<=length; ++x)
2034908d41 2012-05-20        kinaba: 			dp(0,x) = x / LD(walk);
2034908d41 2012-05-20        kinaba: 
2034908d41 2012-05-20        kinaba: 		for(int y=1; y<=width.size(); ++y) {
2034908d41 2012-05-20        kinaba: 			LD w = width[y-1];
2034908d41 2012-05-20        kinaba: 			LD s = speed[y-1];
2034908d41 2012-05-20        kinaba: 
2034908d41 2012-05-20        kinaba: 			for(int x=length,px=length; x>=0; --x) {
2034908d41 2012-05-20        kinaba: 			retry:
2034908d41 2012-05-20        kinaba: 				LD t = dp(y-1, px) + sqrt(LD(px-x)*(px-x) + w*w) / s;
2034908d41 2012-05-20        kinaba: 				if( px > 0 ) {
2034908d41 2012-05-20        kinaba: 					LD tt = dp(y-1, px-1) + sqrt(LD(px-1-x)*(px-1-x) + w*w) / s;
2034908d41 2012-05-20        kinaba: 					if( tt < t ) {
2034908d41 2012-05-20        kinaba: 						--px;
2034908d41 2012-05-20        kinaba: 						goto retry;
2034908d41 2012-05-20        kinaba: 					}
2034908d41 2012-05-20        kinaba: 				}
2034908d41 2012-05-20        kinaba: 				dp(y, x) = t;
2034908d41 2012-05-20        kinaba: 			}
2034908d41 2012-05-20        kinaba: 		}
2034908d41 2012-05-20        kinaba: 
2034908d41 2012-05-20        kinaba: 		return dp(width.size(), length);
2034908d41 2012-05-20        kinaba: 	}
2034908d41 2012-05-20        kinaba: };
2034908d41 2012-05-20        kinaba: 
2034908d41 2012-05-20        kinaba: // BEGIN CUT HERE
2034908d41 2012-05-20        kinaba: #include <ctime>
2034908d41 2012-05-20        kinaba: LD start_time; string timer()
2034908d41 2012-05-20        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
2034908d41 2012-05-20        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
2034908d41 2012-05-20        kinaba:  { os << "{ ";
2034908d41 2012-05-20        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
2034908d41 2012-05-20        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
2034908d41 2012-05-20        kinaba: void verify_case(const LD& Expected, const LD& Received) {
2034908d41 2012-05-20        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
2034908d41 2012-05-20        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
2034908d41 2012-05-20        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
2034908d41 2012-05-20        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
2034908d41 2012-05-20        kinaba: #define END	 verify_case(_, EllysRivers().getMin(length, walk, width, speed));}
2034908d41 2012-05-20        kinaba: int main(){
2034908d41 2012-05-20        kinaba: 
2034908d41 2012-05-20        kinaba: CASE(0)
2034908d41 2012-05-20        kinaba: 	int length = 10;
2034908d41 2012-05-20        kinaba: 	int walk = 3;
2034908d41 2012-05-20        kinaba: 	int width_[] = {5, 2, 3};
2034908d41 2012-05-20        kinaba: 	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
2034908d41 2012-05-20        kinaba: 	int speed_[] = {5, 2, 7};
2034908d41 2012-05-20        kinaba: 	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
2034908d41 2012-05-20        kinaba: 	LD _ = 3.231651964071508;
2034908d41 2012-05-20        kinaba: END
2034908d41 2012-05-20        kinaba: CASE(1)
2034908d41 2012-05-20        kinaba: 	int length = 10000;
2034908d41 2012-05-20        kinaba: 	int walk = 211;
2034908d41 2012-05-20        kinaba: 	int width_[] = {911};
2034908d41 2012-05-20        kinaba: 	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
2034908d41 2012-05-20        kinaba: 	int speed_[] = {207};
2034908d41 2012-05-20        kinaba: 	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
2034908d41 2012-05-20        kinaba: 	LD _ = 48.24623664712219;
2034908d41 2012-05-20        kinaba: END
2034908d41 2012-05-20        kinaba: CASE(2)
2034908d41 2012-05-20        kinaba: 	int length = 1337;
2034908d41 2012-05-20        kinaba: 	int walk = 2;
2034908d41 2012-05-20        kinaba: 	int width_[] = {100, 200, 300, 400};
2034908d41 2012-05-20        kinaba: 	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
2034908d41 2012-05-20        kinaba: 	int speed_[] = {11, 12, 13, 14};
2034908d41 2012-05-20        kinaba: 	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
2034908d41 2012-05-20        kinaba: 	LD _ = 128.57830549575695;
2034908d41 2012-05-20        kinaba: END
2034908d41 2012-05-20        kinaba: CASE(3)
2034908d41 2012-05-20        kinaba: 	int length = 77;
2034908d41 2012-05-20        kinaba: 	int walk = 119;
2034908d41 2012-05-20        kinaba: 	int width_[] = {11, 12, 13, 14};
2034908d41 2012-05-20        kinaba: 	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
2034908d41 2012-05-20        kinaba: 	int speed_[] = {100, 200, 300, 400};
2034908d41 2012-05-20        kinaba: 	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
2034908d41 2012-05-20        kinaba: 	LD _ = 0.3842077071089629;
2034908d41 2012-05-20        kinaba: END
2034908d41 2012-05-20        kinaba: CASE(4)
2034908d41 2012-05-20        kinaba: 	int length = 7134;
2034908d41 2012-05-20        kinaba: 	int walk = 1525;
2034908d41 2012-05-20        kinaba: 	int width_[] = {11567, 19763, 11026, 10444, 24588, 22263, 17709, 11181, 15292, 28895, 15039, 18744, 19985, 13795, 26697, 18812, 25655, 13620, 28926, 12393};
2034908d41 2012-05-20        kinaba: 	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
2034908d41 2012-05-20        kinaba: 	int speed_[] = {1620, 1477, 2837, 2590, 1692, 2270, 1655, 1078, 2683, 1475, 1383, 1153, 1862, 1770, 1671, 2318, 2197, 1768, 1979, 1057};
2034908d41 2012-05-20        kinaba: 	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
2034908d41 2012-05-20        kinaba: 	LD _ = 214.6509731258811;
2034908d41 2012-05-20        kinaba: END
2034908d41 2012-05-20        kinaba: CASE(5)
2034908d41 2012-05-20        kinaba: 	int length = 100000;
2034908d41 2012-05-20        kinaba: 	int walk = 1;
2034908d41 2012-05-20        kinaba: 	int width_[] = {1000000, 1000000, 1000000};
2034908d41 2012-05-20        kinaba: 	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
2034908d41 2012-05-20        kinaba: 	int speed_[] = {1, 1000000, 1};
2034908d41 2012-05-20        kinaba: 	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
2034908d41 2012-05-20        kinaba: 	LD _ = 2000001.004987562;
2034908d41 2012-05-20        kinaba: END
2034908d41 2012-05-20        kinaba: CASE(6)
2034908d41 2012-05-20        kinaba: 	int length = 100000;
2034908d41 2012-05-20        kinaba: 	int walk = 1;
2034908d41 2012-05-20        kinaba: 	int width_[] = {1000000, 1000000, 1000000};
2034908d41 2012-05-20        kinaba: 	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
2034908d41 2012-05-20        kinaba: 	int speed_[] = {1000000, 1000000, 1};
2034908d41 2012-05-20        kinaba: 	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
2034908d41 2012-05-20        kinaba: 	LD _ = 1000002.0024984397;
2034908d41 2012-05-20        kinaba: END
2034908d41 2012-05-20        kinaba: }
2034908d41 2012-05-20        kinaba: // END CUT HERE