fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Work {
  5. 	int S, E, P;
  6. };
  7.  
  8. Work work[10001];
  9. int M, hari_max = 0, memo[10001][10001];
  10.  
  11. int f(int N, int H){
  12. 	if (memo[N][H] != 0){
  13. 		return memo[N][H];
  14. 	}
  15. 	if (N < 1 || H < 1){
  16. 		return 0;
  17. 	} else {
  18. 		if (work[N].E <= H){
  19. 			int ambil = work[N].P + f(N-1, work[N].S - 1);
  20. 			int tidak_ambil = f(N-1, H);
  21. 			memo[N][H] = max(ambil, tidak_ambil);
  22. 			return memo[N][H];
  23. 		} else {
  24. 			memo[N][H] = f(N-1, H);
  25. 			return memo[N][H];
  26. 		}
  27. 	}
  28. }
  29.  
  30. int main() {
  31. 	memset(memo, 0, sizeof(memo));
  32. 	cin >> M;
  33. 	for (int i = 1; i <= M; i++){
  34. 		cin >> work[i].S >> work[i].E >> work[i].P;
  35. 		hari_max = max(hari_max, work[i].E);
  36. 	}
  37.  
  38. 	for (int i = 1; i < M; i++){
  39. 		for (int j = i+1; j <= M; j++){
  40. 			if (work[i].E > work[j].E){
  41. 				swap(work[i], work[j]);
  42. 			}
  43. 		}
  44. 	}
  45.  
  46. 	cout << f(M, hari_max) << endl;
  47.  
  48. 	return 0;
  49. }
Success #stdin #stdout 0.11s 394116KB
comments (?)
stdin
copy 
6
1 5 2000
1 3 500
4 5 700
6 8 800
6 10 3000
9 10 1500
stdout
copy 
5000
https://ideone.com/pHw8fR
language:
C++ (gcc 8.3)
created:
1 day 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!