# Required help RENT Spoj problem

Here is the link of question:

Here is my solution:

``````#include <bits/stdc++.h>
using namespace std;

struct plane
{
int st,dur,rate;
};

int dp[1000001];

bool cmp(plane p1,plane p2)
{
return p1.dur<p2.dur;
}

int findnext(plane arr[],int n)
{
for(int j = n-1;j>=0;j--)
{
if(arr[j].dur<=arr[n-1].st)
{
return j;
}
}
return -1;
}

int solution(plane arr[],int n)
{
// if(n == 1)
// {
// 	return arr[n-1].rate;
// }
// int include = arr[n-1].rate;
// dp[]
// int i = findnext(arr,n);

// if(i!=-1)
// {
// 	include = include+solution(arr,i+1);
// }

// int exclude = solution(arr,n-1);
// return max(include,exclude);
dp[0] = arr[0].rate;
for(int i=1;i<n;i++)
{
int include = arr[i].rate;
int k = findnext(arr,i);
if(k != -1)
{
include = include+dp[k];
}
int exclude = dp[i-1];
dp[i] = max(include,exclude);
}
return dp[n-1];
}

int main() {
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
int n;
cin>>n;
struct plane arr[n];
for(int i=0;i<n;i++)
{
int s,e,p;
cin>>s>>e>>p;
arr[i].st = s;
arr[i].dur = s+e;
arr[i].rate = p;
}

sort(arr,arr+n,cmp);

int ans = solution(arr,n);
cout<<ans<<endl;
}
return 0;
}
``````