Overview
| SHA1 Hash: | 8afddeabcfe5f5d59a696342ca1de4932ed83d1b |
|---|---|
| Date: | 2011-09-21 12:37:55 |
| User: | kinaba |
| Comment: | 518 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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 };