• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/518-U/1A.cpp version [39f7d6474ae7b753]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class LargestSubsequence { public:
           23  +  string getLargest(string s)
           24  +  {
           25  +    string result;
           26  +    for(string::iterator it=s.begin(); it!=s.end(); ) {
           27  +      it = max_element(it, s.end());
           28  +      if( it != s.end() )
           29  +        result += *it++;
           30  +    }
           31  +    return result;
           32  +  }
           33  +};

Added SRM/518-U/1B.cpp version [3c712bb16a6c8631]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class ConvexSequence { public:
           23  +  long long getMinimum(vector <int> a)
           24  +  {
           25  +    int i = min_element(a.begin(), a.end()) - a.begin();
           26  +    vector<LL> pre(a.begin(), a.begin()+i+1);
           27  +    reverse(pre.begin(), pre.end());
           28  +    vector<LL> post(a.begin()+i, a.end());
           29  +    return convex_incr(pre) + convex_incr(post);
           30  +  }
           31  +
           32  +  LL convex_incr(vector<LL> a)
           33  +  {
           34  +    if( a.empty() )
           35  +      return 0;
           36  +    for(int i=a.size()-1; i>=0; --i)
           37  +      a[i] -= a[0];
           38  +
           39  +    LL cnt = 0;
           40  +    for(int i=1; i<a.size()-1; ++i)
           41  +    {
           42  +      LL amax = a[i];
           43  +      for(int k=i+1; k<a.size(); ++k)
           44  +        amax = min(amax, (a[k] - a[i-1]) / (k-(i-1)) + a[i-1]);
           45  +      if( amax < a[i] ) {
           46  +        cnt += a[i]-amax;
           47  +        a[i] = amax;
           48  +      }
           49  +    }
           50  +    return cnt;
           51  +  }
           52  +};