Artifact 3c712bb16a6c8631c6da6c5ef8c17e64de41ec5e

• File SRM/518-U/1B.cpp
  • 2011-09-21 12:37:55 - part of checkin [8afddeabcf] on branch trunk - 518 (user: kinaba) [annotate]
• File SRM/518/1B.cpp
  • 2011-09-28 15:32:27 - part of checkin [14e544f8d9] on branch trunk - rename (user: kinaba) [annotate]

#include <iostream> 
#include <sstream> 
#include <iomanip> 
#include <vector> 
#include <string> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <numeric> 
#include <iterator> 
#include <functional> 
#include <complex> 
#include <queue> 
#include <stack> 
#include <cmath> 
#include <cassert> 
#include <cstring> 
using namespace std; 
typedef long long LL; 
typedef complex<double> CMP; 

class ConvexSequence { public: 
  long long getMinimum(vector <int> a) 
  { 
    int i = min_element(a.begin(), a.end()) - a.begin(); 
    vector<LL> pre(a.begin(), a.begin()+i+1); 
    reverse(pre.begin(), pre.end()); 
    vector<LL> post(a.begin()+i, a.end()); 
    return convex_incr(pre) + convex_incr(post); 
  } 

  LL convex_incr(vector<LL> a) 
  { 
    if( a.empty() )  
      return 0; 
    for(int i=a.size()-1; i>=0; --i) 
      a[i] -= a[0]; 

    LL cnt = 0; 
    for(int i=1; i<a.size()-1; ++i) 
    { 
      LL amax = a[i]; 
      for(int k=i+1; k<a.size(); ++k) 
        amax = min(amax, (a[k] - a[i-1]) / (k-(i-1)) + a[i-1]); 
      if( amax < a[i] ) { 
        cnt += a[i]-amax; 
        a[i] = amax; 
      } 
    } 
    return cnt; 
  } 
};