TopCoder Single Round Match 543 Division I 500 EllysRivers

EllysRivers.cpp

#line 103 "EllysRivers.cpp"
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin)
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define tr(c, i) for(iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

typedef long long ll;

const static int inf = 1e18;
const static int mod = 1000000007;

vector<double> step;
int walk;

int abs(int i) {
  if(i > 0) {
    return i;
  }else {
    return -i;
  }
}

void update(const vector<double>& now, vector<double>& next, int ls, int lt, int rs, int rt) {
  if(rs > rt) {
    return;
  }
  int mid = (rs+rt)/2;
  double mn = inf;
  int pos = ls;
  for(int i = ls; i <= lt; ++i)  {
    double buf = now[i]+step[abs(i-mid)];
    if(mn > buf) {
      mn = buf;
      pos = i;
    }
  }
  next[mid] = mn;
  update(now, next, ls, pos, rs, mid-1);
  update(now, next, pos, lt, mid+1, rt);
}

class EllysRivers {
  public:
  double getMin(int l, int walk, vector <int> w, vector <int> s) {
    int n = w.size();
    vector<double> now(l+1);
    rep(i, l+1) {
      now[i] = (double)i/walk;
    }
    rep(i, n) {
      vector<double> next(l+1);
      step.clear(); step.resize(l+1);
      rep(j, l+1) {
	step[j] = sqrt(((double)w[i]*(double)w[i] + (double)j*(double)j)) / s[i];
      }
      update(now, next, 0, l, 0, l);
      swap(now, next);
    }

    double ans = inf;
    rep(i, l+1) {
      ans = min(ans, now[i]+(double)(l-i)/walk);
    }
    return ans;
  }
};