Guest User

Untitled

a guest
Sep 7th, 2019
330
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <deque>
  3. #include <utility>
  4. using namespace std;
  5. typedef pair<long long,long long> ll;
  6. int n,k; ///n is arr size, k is number of groups to split arr into
  7. long long arr[20005]; ///our original array
  8. long long pre[20005];
  9. long long val, groups; ///for returning value once convex_hull() is called
  10. struct linear_hull{
  11.     deque<ll> dq;
  12.     deque<long long> cuts;
  13.     double intercept (ll i, ll j){
  14.         return ((double)(j.second-i.second))/((double)(i.first-j.first));
  15.     }
  16.     void remove(double i){
  17.         ll _front=dq.front();
  18.         dq.pop_front();
  19.         while (!dq.empty() && intercept(_front,dq.front())<=i){
  20.             _front=dq.front();
  21.             dq.pop_front();
  22.             cuts.pop_front();
  23.         }
  24.         dq.push_front(_front);
  25.     }
  26.     void add(ll i,long long j){
  27.         if (!dq.empty()){
  28.             ll _back=dq.back();
  29.             dq.pop_back();
  30.             while (!dq.empty() && intercept(i,dq.back())<= intercept(_back,dq.back())){
  31.                 _back=dq.back();
  32.                 dq.pop_back();
  33.                 cuts.pop_back();
  34.             }
  35.             dq.push_back(_back);
  36.         }
  37.         dq.push_back(i);
  38.         cuts.push_back(j);
  39.     }
  40.     void init(){
  41.         dq.clear();
  42.         cuts.clear();
  43.     }
  44.     long long get(long long x){
  45.         this->remove(x);
  46.         return dq.front().first*x+dq.front().second;
  47.     }
  48.     long long getcuts(){
  49.         return cuts.front();
  50.     }
  51. } *hull=new linear_hull();
  52. //so we know how many cuts is used when doing our linear convex hull
  53.  
  54. void lagrangian_multiplier(long long cost){
  55.     hull->init();
  56.     hull->add(ll(0,0),1);
  57.     long long best;
  58.     for (long long x=1;x<n;x++){
  59.         best=hull->get(pre[x])+pre[x]*pre[x];
  60.         hull->add(ll(-2*pre[x],best+pre[x]*pre[x]+cost),(hull->getcuts())+1);
  61.     }
  62.     val=hull->get(pre[n])+pre[n]*pre[n];
  63.     groups=hull->getcuts();
  64. }
  65.  
  66. int main(){
  67.     scanf("%d%d",&n,&k);
  68.     for (int x=1;x<=n;x++) scanf("%d",&arr[x]);
  69.     for (int x=1;x<=n;x++) pre[x]=arr[x]+pre[x-1];
  70.     long long a=0,b=(long long)200000000000005,c;
  71.     while (a!=b){
  72.         c=(a+b)>>1;
  73.         lagrangian_multiplier(c);
  74.         if (groups>k){
  75.             a=c+1;
  76.         }
  77.         else if (groups<k){
  78.             b=c;
  79.         }
  80.         else{
  81.             ///we have found a optimal cost, c to spilt into k groups
  82.             break;
  83.         }
  84.     }
  85.     printf("%lld\n",val-(groups-1)*c); ///rmb to minus the extra cost in lagrange speedup to get the actual value
  86. }
RAW Paste Data