fork download
copy 
  1. #include <bits/stdc++.h>
  2. 		using namespace std;
  3. 		struct piatto{
  4. 			int s;
  5. 			int e;
  6. 			int w;
  7. 	};
  8. 		int main(){
  9. 			int N;
  10. 			cin >> N;
  11. 			vector<piatto>V(N+1);
  12. 			V[0]={-1, -1, 0};
  13. 			for(int i = 1; i <= N; i++){
  14. 				int S, W, D;
  15. 				cin >> S >> W >> D;
  16. 				V[i]={S, D + S, W};
  17. 			}
  18. 			sort(V.begin(), V.end(), [](const piatto a, const piatto b){
  19. 				return a.e < b.e;
  20. 			});
  21. 			vector<int>DP(N + 1, 0);
  22. 			for(int i = 1; i <= N; i++){
  23. 				auto it = upper_bound(V.begin(), V.begin() + i, V[i].s, [](const int v, const  piatto a){
  24. 					return a.e > v;
  25. 				});
  26. 				//primo elemento con a.e > v[i].s
  27.  
  28. 				int idx = it - V.begin();
  29. 				idx--;
  30. 			//	cout << "\t " << V[i].s << " " << V[i].e << " " << V[i].w <<"idx: "<<idx <<endl;
  31. 				DP[i] = max(DP[i - 1], DP[idx] + V[i].w);		
  32.  
  33.  
  34. 			}
  35. 			int ret = *max_element(DP.begin(), DP.end());
  36. 			cout << ret << endl;
  37. 		}
  38.  
  39.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
3
1 5 3
4 8 6
4 7 5
stdout
copy 
13
https://ideone.com/yoULde
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

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!