14e544f8d9 2011-09-28        kinaba: #include <iostream>
14e544f8d9 2011-09-28        kinaba: #include <sstream>
14e544f8d9 2011-09-28        kinaba: #include <iomanip>
14e544f8d9 2011-09-28        kinaba: #include <vector>
14e544f8d9 2011-09-28        kinaba: #include <string>
14e544f8d9 2011-09-28        kinaba: #include <map>
14e544f8d9 2011-09-28        kinaba: #include <set>
14e544f8d9 2011-09-28        kinaba: #include <algorithm>
14e544f8d9 2011-09-28        kinaba: #include <numeric>
14e544f8d9 2011-09-28        kinaba: #include <iterator>
14e544f8d9 2011-09-28        kinaba: #include <functional>
14e544f8d9 2011-09-28        kinaba: #include <complex>
14e544f8d9 2011-09-28        kinaba: #include <queue>
14e544f8d9 2011-09-28        kinaba: #include <stack>
14e544f8d9 2011-09-28        kinaba: #include <cmath>
14e544f8d9 2011-09-28        kinaba: #include <cassert>
14e544f8d9 2011-09-28        kinaba: #include <cstring>
14e544f8d9 2011-09-28        kinaba: using namespace std;
14e544f8d9 2011-09-28        kinaba: typedef long long LL;
14e544f8d9 2011-09-28        kinaba: typedef complex<double> CMP;
14e544f8d9 2011-09-28        kinaba: 
14e544f8d9 2011-09-28        kinaba: class ConvexSequence { public:
14e544f8d9 2011-09-28        kinaba:   long long getMinimum(vector <int> a)
14e544f8d9 2011-09-28        kinaba:   {
14e544f8d9 2011-09-28        kinaba:     int i = min_element(a.begin(), a.end()) - a.begin();
14e544f8d9 2011-09-28        kinaba:     vector<LL> pre(a.begin(), a.begin()+i+1);
14e544f8d9 2011-09-28        kinaba:     reverse(pre.begin(), pre.end());
14e544f8d9 2011-09-28        kinaba:     vector<LL> post(a.begin()+i, a.end());
14e544f8d9 2011-09-28        kinaba:     return convex_incr(pre) + convex_incr(post);
14e544f8d9 2011-09-28        kinaba:   }
14e544f8d9 2011-09-28        kinaba: 
14e544f8d9 2011-09-28        kinaba:   LL convex_incr(vector<LL> a)
14e544f8d9 2011-09-28        kinaba:   {
14e544f8d9 2011-09-28        kinaba:     if( a.empty() )
14e544f8d9 2011-09-28        kinaba:       return 0;
14e544f8d9 2011-09-28        kinaba:     for(int i=a.size()-1; i>=0; --i)
14e544f8d9 2011-09-28        kinaba:       a[i] -= a[0];
14e544f8d9 2011-09-28        kinaba: 
14e544f8d9 2011-09-28        kinaba:     LL cnt = 0;
14e544f8d9 2011-09-28        kinaba:     for(int i=1; i<a.size()-1; ++i)
14e544f8d9 2011-09-28        kinaba:     {
14e544f8d9 2011-09-28        kinaba:       LL amax = a[i];
14e544f8d9 2011-09-28        kinaba:       for(int k=i+1; k<a.size(); ++k)
14e544f8d9 2011-09-28        kinaba:         amax = min(amax, (a[k] - a[i-1]) / (k-(i-1)) + a[i-1]);
14e544f8d9 2011-09-28        kinaba:       if( amax < a[i] ) {
14e544f8d9 2011-09-28        kinaba:         cnt += a[i]-amax;
14e544f8d9 2011-09-28        kinaba:         a[i] = amax;
14e544f8d9 2011-09-28        kinaba:       }
14e544f8d9 2011-09-28        kinaba:     }
14e544f8d9 2011-09-28        kinaba:     return cnt;
14e544f8d9 2011-09-28        kinaba:   }
14e544f8d9 2011-09-28        kinaba: };