SRM339Div2

250

class BettingStrategy {
public:
  int finalSum(int sum, string o) {
    int bet = 1;
    for(int i=0; i<o.size(); ++i){ 
      if(sum < bet)break;
      if( o[i] == 'W' ){
        sum += bet;
        bet = 1;
      }
      else{
        sum -= bet;
        bet *= 2;
      }
    }
    return sum;
  }
};

500
んー？

1000

struct E{
  int src, dst, dep, time, cost;  
};
bool operator < (E a, E b)
{
  return a.dep < b.dep;
}

class OnTime {
public:
  int minCost(int N, int T, vector <string> buses) {
    const int inf = 1 << 25;
    const int B = buses.size();

    int t[N+1][T+1];
    fill( &t[0][0], &t[N][T+1], inf );

    E e[B];
    for(int i=0; i<buses.size(); ++i){
      istringstream iss( buses[i] );
      iss >> e[i].src >> e[i].dst >> e[i].dep >> e[i].time >> e[i].cost;
    }
    sort( e, e + B );

    for(int i=0; i<=T; ++i){
      t[0][i] = 0;
    }
    for(int i=0; i<B; ++i){
      if( e[i].dep + e[i].time <= T ){
        int &n = t[ e[i].dst ][ e[i].dep + e[i].time ];
        int m = e[i].src == 0;
        for(int j=0; j<e[i].dep+m; ++j){
          n = min( n, t[ e[i].src ][ j ] + e[i].cost );
        }
      }
    }

    int mn = inf;
    for(int i=0; i<=T; ++i){
      mn = min( mn, t[N-1][i] );
    }
    return mn == inf ? -1 : mn;
  }
};