fork download 
  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. 			int idx = it - V.begin();	
  27. 		        DP[i] = max(DP[i - 1], DP[idx-1] + V[i].w);		
  28.  
  29.  
  30. 			}
  31. 			int ret = *max_element(DP.begin(), DP.end());
  32. 			cout << ret << endl;
  33. 		}
  34.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
4
6 24 3
8 16 5
12 14 1
9 11 4
stdout 
38
https://ideone.com/bxPBVP
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!