SRM348Div2

250

class OptimalList {
public:
  string optimize(string s) {

    string t;
    int i, j;
    i = j = 0;
    for(int k=0; k<s.size(); ++k){
      if( s[k] == 'S' )++i;
      else if( s[k] == 'N' )--i;
      else if( s[k] == 'W' )--j;
      else if( s[k] == 'E' )++j;
    }
    while( 0 < j ){ t += 'E'; --j; }
    while( 0 < i ){ t += 'S'; --i; }
    while( i < 0 ){ t += 'N'; ++i; }
    while( j < 0 ){ t += 'W'; ++j; }
    return t;
  }
};

500

class LostParentheses {
public:
  int minResult(string e) {

    vector<int> num;
    vector<char> op;

    if( e[0] == '-' ) e = "0" + e;

    for(int i=0; i<e.size(); ++i){
      if( e[i] == '+' || e[i] == '-' )op.push_back( e[i] );
    }
    replace( e.begin(), e.end(), '+', ' ' );
    replace( e.begin(), e.end(), '-', ' ' );

    istringstream iss( e );
    for(int n; iss >> n; num.push_back(n));

    for(int i=(int)op.size()-1; 0<=i; --i){
      if( op[i] == '+' ){
        num[i] += num[i+1];
    num[i+1] = 0;
      }
    }

    int ret = num[0];
    for(int i=1; i<num.size(); ++i){
      ret -= num[i];
    }

    return ret;
  }
};

1000

class IncreasingSubsequences {
public:
  long long count(vector <int> a) {

    const int size = a.size();
    bool g[ size ][ size ];
    fill( &g[0][0], &g[size-1][size], false );

    for(int i=0; i<size; ++i){
      for(int j=i+1; j<size; ++j){
        if( a[i] < a[j] ); else continue;
        bool flg = false;
        for(int k=i+1; k<j; ++k){
          flg = flg || ( a[i] < a[k] && a[k] < a[j]);
        }
        if( !flg )g[i][j] = true;
      }
    }

    lli t[ size ];
    for(int i=0; i<size; ++i){
      bool flg = false;
      for(int j=0; j<i; ++j){
        flg = flg || a[j] < a[i];
      }
      t[i] = flg ? 0 : 1;
    }

    for(int i=0; i<size; ++i){
      for(int j=i+1; j<size; ++j){
        if( g[i][j] ){
          t[j] += t[i];
        }
      }
    }

    lli sum = 0;
    for(int i=0; i<size; ++i){
      bool flg = false;
      for(int j=0; j<size; ++j){
        flg = flg || g[i][j];
      }
      if( !flg )sum += t[i];
    }

    return sum;
  }
};