题目连接

我的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+9;
int n,k,a;
struct node{
	int x,y,c;
} p[N];
int nxt[N],hd[N];
int dp[N],g[N*5],tag[N*5];
void pushdown(int nn,int ln,int rn){
	if(!tag[nn])
		return;
	tag[ln]+=tag[nn];
	g[ln]+=tag[nn];
	tag[rn]+=tag[rn];
	g[rn]+=tag[nn];
	tag[nn]=0;
}
void pushup(int nn,int ln,int rn){
	g[nn]=max(g[ln],g[rn]);
}
void add(int now,int nl,int nr,int l,int r,int num){
	if(l<=nl&&nr<=r){
		g[now]+=num;
		tag[now]+=num;
		return;
	}
	if(nr<l||nl>r)
		return;
	int ln,rn,mid;
	ln=now*2;rn=now*2+1;mid=(nl+nr)/2;
	pushdown(now,ln,rn);
	add(ln,nl,mid,l,r,num);
	add(rn,mid+1,nr,l,r,num);
	pushup(now,ln,rn);
	return;
}
int main(){
	int sum=0;
	cin>>n>>k>>a;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y>>p[i].c;
		sum+=p[i].c;
		nxt[i]=hd[p[i].y];
		hd[p[i].y]=i;
	}
	node now;
	for(int i=1,j=k-1;i<=k;i++,j--){
		for(int t=hd[j];t;t=nxt[t]){
			now=p[t];
			add(1,0,k,0,now.x,now.c);
		}
		add(1,0,k,0,i-1,-a);
		dp[i]=max(dp[i-1],g[1]);
		add(1,0,k,i+1,i+1,dp[i]);
	}
	cout<<sum-dp[k]<<endl;
	return 0;
}