fork(1) download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6. long long int dp[2][10003];
  7. long long int data[10003];
  8. int main() {
  9. 	// your code goes here
  10. 	int n,m;
  11. 	memset(dp,0,sizeof(dp));
  12. 	memset(data,0,sizeof(data));
  13. 	cin>>n>>m;
  14. 	for(int i=0;i<n;i++){
  15. 		cin>>data[i];
  16. 	}
  17.  
  18. 	for(int i=0;i<n;i++){
  19. 		for(int j=max(0,i-m+1);j<i;j++){
  20. 			dp[0][i+m]=max(dp[0][i+m],dp[1][j]+data[i]);
  21. 			dp[1][j+m]=max(dp[1][i],dp[1][j]+data[i]);
  22. 		}	
  23. 		for(int j=0;j<=i;j++){
  24. 			dp[1][i]=max(dp[1][i],dp[0][j]+data[i]);
  25. 			dp[0][i+m]=max(dp[0][i+m],dp[0][j]+data[i]);
  26. 		}
  27. 		for(int j=0;j<2;j++){
  28. 			dp[j][i+1]=max(dp[j][i+1],dp[j][i]);
  29. 		}
  30. 		//for(int j=0;j<10;j++){
  31. 		//	cout<<j<<"("<<dp[0][j]<<" "<<dp[1][j]<<")";
  32. 		//}
  33. 		//cout<<endl;
  34. 	}
  35. 	long long int ans=0;
  36. 	for(int i=0;i<2*n+3;i++){
  37. 		for(int j=0;j<2;j++){
  38. 			ans=max(ans,dp[j][i]);
  39. 		}
  40. 	}
  41. 	cout<<ans<<endl;
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
6 3
3 7 1 5 6 4
stdout
copy 
20
https://ideone.com/pFVH3X
language:
C++ (gcc 8.3)
created:
7 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!