dp - Convex Hull - Deque

/********************** CONVEX HULL TRICK ***********************************
1. Not normal Slope.
2. Using deque
3. Problem: https://vjudge.net/problem/HDU-3045
****************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define LL                      long long

const int N = 400006;
int n,T;
LL dp[N];
LL sum[N];
LL a[N];
LL calc(int k){ return dp[k] - sum[k] + a[k+1]*k;}
int main()
{
      while(scanf("%d %d",&n,&T)==2){
            for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
            sort(a+1,a+n+1);
            for(int i=1;i<=n;i++) sum[i] = a[i] + sum[i-1] ;
            dp[0]=0;
            sum[0]=0;


            deque<int> q;
            q.push_back(0);
            for(int i=T; i<= n;i ++) {
                  while(q.size() > 1 ) {
                        int k = q[0] , j = q[1];
                        if( calc(j) - calc(k) <= i * (a[j+1] - a[k+1])) q.pop_front();
                        else break;
                  }
                  int j = q.front();
                  dp[i] = dp[j] + sum[i] - sum[j] - a[j+1]*(i-j);
                  j = i-T+1;
                  if(j < T) continue;
                  while(q.size()>1) {
                        int k = q[q.size()-1],  l = q[q.size()-2];
                        if( (calc(j) - calc(k)) * (a[k+1] - a[l+1]) <= (calc(k) - calc(l)) * (a[j+1] - a[k+1])  ) q.pop_back();
                        else break;
                  }
                  q.push_back(j);
            }
            cout << dp[n] << endl;
      }
      return 0;
}