#include<stdio.h>
#include<stdlib.h>
#include<math.h>
long long ans;
struct trainer{
int t,d,s;
}arr[100001],temp;
void maxheapify(struct trainer arr,int i,int N){
int largest;
int left =2i;
int right=2*i+1;
if(left<=N&&arr.s>arr[i].s)
largest=left;
else largest=i;
if(right<=N&&arr[right].s>arr[largest].s)
largest=right;
if(largest!=i){
temp=arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
maxheapify(arr,largest,N);
}
}
void buildmaxheap(struct trainer *arr,int N){
int i;
for(i=N/2;i>=1;i–){
maxheapify(arr,i,N);
}
}
int main(){
int T,N,D,i,n,j,k;
scanf("%d\n",&T);
while(T){ans=0;
scanf("%d %d\n",&N,&D);
for(i=1;i<=N;i++)
scanf("%d %d %d\n",&arr[i].d,&arr[i].t,&arr[i].s);
int *rd=(int )malloc(sizeof(int)(D+1));
i=1;
j=D;
while(j&&i<=D){
rd[i]=j;
i++;
j–;
}
/for(i=1;i<=D;i++)
printf("%d “,rd[i]);
printf(”\n");/
buildmaxheap(arr,N);
n=N;
i=1;
while(i<=N){
if(rd[arr[1].d]>=arr[1].t){
j=arr[1].d;
while(j>0){
rd[j]=rd[j]-arr[1].t;
j–;
}
j=arr[1].d+1;
while(j<=D){
if(D-j+1>=rd[arr[1].d])
rd[j]=rd[arr[1].d];
else
rd[j]=D-j+1;
j++;
}
}
else{
ans=ans+arr[1].s*(arr[1].t-rd[arr[1].d]);
j=arr[1].d;
k=rd[arr[1].d];
while(j>0){
rd[j]=rd[j]-k;
j--;
}
j=arr[1].d+1;
while(j<=D){
if(D-j+1>=rd[arr[1].d])
rd[j]=rd[arr[1].d];
else
rd[j]=D-j+1;
j++;
}
}
//exchange(arr,1,n-i+1);
temp=arr[1];
arr[1]=arr[n-i+1];
arr[n-i+1]=temp;
if(n-i>1)
maxheapify(arr,1,n-i);
i++;
}
printf("%lld\n",ans);
/* for(i=1;i<=D;i++)
printf("%d ",rd[i]);
printf("\n");*/
T--;
}
return 0;
}
. I will try again later, to find where you are getting WA.