fork download
copy 
  1. #include <iostream>
  2. #include <climits>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. bool mycompare(int a, int b) {
  9. 	return a>b;
  10. }
  11.  
  12. int main() {
  13.  
  14. 	int t;
  15. 	cin >> t;
  16. 	while(t--) {
  17. 		int k,n;
  18. 		cin >> k >> n;
  19.  
  20. 		int arr[n];
  21. 		for(int i=0; i<n; i++) 
  22. 			cin >> arr[i];
  23.  
  24. 		int local_min = 0, local_max = 0;
  25. 		int ptr=0;
  26. 		vector<int> trans;
  27. 		while(ptr<(n-1)) {
  28. 			//local minima
  29. 			while( ptr<(n-1) && arr[ptr]>arr[ptr+1])
  30. 				ptr++;
  31. 			if(ptr == (n-1)){
  32. 				local_min = -1;
  33. 				break;
  34. 			}
  35.  
  36. 			local_min = ptr;
  37.  
  38. 			//local max
  39. 			while( ptr<(n-1) && arr[ptr]<arr[ptr+1])
  40. 				ptr++;
  41.  
  42. 			local_max = ptr;
  43. 			int tran = arr[local_max]-arr[local_min];
  44. 			trans.push_back(tran);
  45. 		}
  46.  
  47. 		if(trans.size() <= k){
  48. 			int ans = 0;
  49. 			for(int i=0; i<trans.size(); i++){
  50. 				ans += trans[i];
  51. 			}
  52. 			cout << ans << endl;
  53. 		}else {
  54. 			int ans=0;
  55. 			sort(trans.begin(), trans.end(), mycompare);
  56. 			for(int i=0; i<k; i++) {
  57. 				ans += trans[i];
  58. 			}
  59. 			cout << ans << endl;
  60. 		}
  61.  
  62. 	}
  63.  
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 4312KB
comments (?)
stdin
copy 
1
1 7 100 180 260 310 40 535 695
stdout
copy 
655
https://ideone.com/rRMoGs
language:
C++ (gcc 8.3)
created:
5 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!