K-Anonymous Sequence POJ

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N= 500000+10;
int q[N],l,r;
ll sum[N],val[N];
ll dp[N];
int n,m;
ll getdown(int j,int k) {
	return val[j+1]-val[k+1];
}

ll getup(int j,int k) {
	return (dp[j]-sum[j]+j*val[j+1])-(dp[k]-sum[k]+k*val[k+1]);
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d",&n,&m);
		memset(dp,0,sizeof dp);
		memset(sum,0,sizeof sum);
		memset(val,0,sizeof val);
		for(int i=1; i<=n; i++)
			scanf("%lld",&val[i]);
		sort(val+1,val+1+n);
		for(int i=1; i<=n; i++)
			sum[i]=sum[i-1]+val[i];
		l=r=0;
		q[0]=0;
		for(int i=2; i<=n; i++) {
			while(l<r && getup(q[l+1],q[l])<=getdown(q[l+1],q[l])*i)
				l++;
			int j=q[l];
			dp[i]=dp[j]+(sum[i]-sum[j])-(i-j)*val[j+1];
			j=i-m+1;
			if(j<m)
				continue;
			while(l<r && getup(q[r],q[r-1])*getdown(j,q[r-1])>= getup(j,q[r-1])*getdown(q[r],q[r-1]))
				r--;
			q[++r]=j;
		}
		printf("%lld
",dp[n]);
	}
}