SRM346Div2

250

class DiamondHunt {
public:
  int countDiamonds(string mine) {
    int cnt = 0;
    stack<char> s;
    for(int i=0; i<mine.size(); ++i){
      if( s.empty() ) s.push( mine[i] );
      else{
        if( s.top() == '<' && mine[i] == '>' ){
          ++cnt;
          s.pop();
        }
        else s.push( mine[i] );
      }
    }
    return cnt;
  }
};

500

1000

class FastPostman {
public:
  int minTime(vector <int> address, vector <int> maxTime, int initialPos) {

    const int size = address.size();
    pair<int, int> p[size];

    for(int i=0; i<size; ++i){
      p[i] = make_pair( address[i], maxTime[i] );
    }

    sort( p, p + size );

    const int inf = 1 << 25;
    const int RIGHT = 0;
    const int LEFT = 1;
    
    int t[size][size][2];    

    fill( &t[0][0][0], &t[size-1][size-1][2], inf );

    for(int i=0; i<size; ++i){
      t[i][i][LEFT] = t[i][i][RIGHT] = abs( p[i].first - initialPos );
      if( p[i].second < t[i][i][LEFT] ) t[i][i][LEFT] = inf;
      if( p[i].second < t[i][i][RIGHT] ) t[i][i][RIGHT] = inf;
    }
    
    for(int right = 0; right < size; ++right){
      for(int left = right; 0 <= left; --left){
        for(int pos = 0; pos < 2; ++pos){

          int curr = pos ? left : right;

          int next_left = left - 1;
          int next_right = right + 1;
          
          if( 0 <= next_left ){
            int cost = abs( p[next_left].first - p[curr].first );
            if( t[left][right][pos] + cost <= p[next_left].second ){
              t[next_left][right][LEFT] = min( t[next_left][right][LEFT], t[left][right][pos] + cost );
            }
          }
          if( next_right < size ){
            int cost = abs( p[next_right].first - p[curr].first );
            if( t[left][right][pos] + cost <= p[next_right].second ){
              t[left][next_right][RIGHT] = min( t[left][next_right][RIGHT], t[left][right][pos] + cost );
            }
          }

        }
      }
    }
    
    int ret = min( t[0][size-1][LEFT], t[0][size-1][RIGHT] );
    return ret == inf ? -1 : ret;
  }
};