uva11285 uvalive3983 Hackers' Crackdown

uva11285 uvalive3983 Hackers' Crackdown
// AC
// A.myc
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=100005;
struct dpnode{
	int idx;
	int val;
};
dpnode queue[maxn];
int head,tail;
int dp[maxn];
int s[maxn];
int d[maxn];
int w[maxn];
int c,n;
void Dp(){
	head=tail=0;
	memset(dp,-1,sizeof(dp));
	dp[0]=0; dp[1]=2*d[1];
	queue[tail].idx=0; queue[tail++].val=dp[0];
	queue[tail].idx=1; queue[tail++].val=dp[1]; // ##
	for(int i=2;i<=n;i++){
		while((w[i]-w[queue[head].idx])>c) head++; // ##
		for(int j=head;queue[j].idx<i && j!=tail;j++){
			if(w[i]-w[queue[j].idx]<=c && (dp[i]==-1 || (dp[queue[j].idx]+d[queue[j].idx+1]+s[i]-s[queue[j].idx+1]+d[i])<dp[i])){
				dp[i]=(dp[queue[j].idx]+d[queue[j].idx+1]+s[i]-s[queue[j].idx+1]+d[i]);
			}
		}
		while(i<n && (dp[i]+d[i+1]-s[i+1])<(queue[tail-1].val+d[queue[tail-1].idx+1]-s[queue[tail-1].idx+1]) && tail>head) tail--;
		queue[tail].idx=i; queue[tail++].val=dp[i];
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&c,&n);
		int x0=0,y0=0; s[0]=0; w[0]=0;
		for(int i=1;i<=n;i++){
			int x,y;
			scanf("%d%d%d",&x,&y,&w[i]);
			d[i]=x+y; s[i]=s[i-1]+abs((double)x-x0)+abs((double)y-y0);
			w[i]+=w[i-1];
			x0=x,y0=y;
		}
		Dp();
		printf("%d\n",dp[n]);
		if(T>0) printf("\n"); // ##
	}
	return 0;
}