fork(1) download 
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. struct job{
  5. 	int start,finish,profit;
  6. };
  7. bool func(job s1,job s2){
  8. 	return (s1.start<s2.start);
  9. }
  10. int binsearch(job a[],int st,int en,int val){
  11. 	while(st<en){
  12. 		int mid=(st+en)/2;
  13. 		if(a[mid].start>=val)
  14. 			en=mid;
  15. 		else
  16. 			st=mid+1;
  17. 	}
  18. 	if(a[st].start >=val) return st;
  19. 	else return -1;
  20. }
  21. int main(){
  22. 	int t,n,d,mm,m1;
  23. 	cin>>t;
  24. 	while(t--){
  25. 		cin>>n;
  26. 		job ar[n];
  27. 		int pro[n+1]={0},m;
  28. 		for(int i=0;i<n;i++){
  29. 			cin>>ar[i].start>>d>>ar[i].profit;
  30. 			ar[i].finish=ar[i].start+d;
  31. 			}
  32.         /*r(int i=0;i<n;i++)
  33.             cout<<ar[i].start<<" "<<ar[i].finish<<" "<<ar[i].profit<<endl;*/
  34. 		sort(ar,ar+n,func);
  35. 		for(int i=n-1;i>=0;i--){
  36. 			pro[i]=pro[i+1];
  37. 			mm=binsearch(ar,i+1,n-1,ar[i].finish);
  38.             if(mm==-1) m1=0;
  39.             else m1=pro[mm];
  40. 		     if(m1+ar[i].profit > pro[i])
  41. 					pro[i]=pro[mm]+ar[i].profit;
  42. 		}
  43. 		cout<<pro[0]<<endl;
  44. 	}
  45. 	return 0;
  46. }
  47.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
1
4
0 5 10
3 7 14
5 9 7
6 9 8
stdout 
134515454
https://ideone.com/UgnBRN
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!