fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  5. long long int dp[2][10001];
  6. long long int xs[10001];
  7. int main() {
  8. 	memset(dp,0,sizeof(dp));
  9. 	memset(xs,0,sizeof(xs));
  10. 	int n,k;
  11. 	cin>>n>>k;
  12. 	for(int i=0;i<n;i++){
  13. 		cin>>xs[i];
  14. 	}
  15. 	for(int i=0;i<n;i++){
  16. 		for(int j=i;j<n;j++){
  17. 			dp[1][j+1]=max(dp[1][j+1],dp[0][i]+xs[j]);
  18. 			dp[0][j+k]=max(dp[0][j+k],dp[0][i]+xs[j]);
  19. 		}
  20. 		for(int j=i;j<n;j++){
  21. 			if(j<i+k){
  22. 				//if(i==1)cout<<"("<<i<<" "<<j<<" "<<k<<")";
  23. 				dp[1][i+k]=max(dp[1][i+k],dp[1][i]+xs[j]);
  24. 				dp[0][j+k]=max(dp[0][j+k],dp[1][i]+xs[j]);
  25. 			}else{
  26. 				//if(i==1)cout<<"("<<i<<" "<<j<<")";
  27. 				dp[1][j+1]=max(dp[1][j+1],dp[1][i]+xs[j]);
  28. 				dp[0][j+k]=max(dp[0][j+k],dp[1][i]+xs[j]);
  29. 				dp[0][i+k]=max(dp[0][i+k],dp[1][i]);
  30. 			}
  31. 		}
  32. 	}
  33. 	long long int ans=0;
  34. 	for(int i=0;i<10000;i++){
  35. 		if(ans<dp[0][i])ans=dp[0][i];
  36. 		if(ans<dp[1][i])ans=dp[1][i];
  37. 		//cout<<"("<<i<<","<<dp[0][i]<<","<<dp[1][i]<<")";
  38. 	}
  39. 	cout<<ans<<endl;
  40. 	return 0;
  41. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
20 2
924627176 831397340 164783720 215543892 979742980 924963038 634722211 747236231 495518691 605527991 968366382 706204608 828466032 277983427 165214607 321943325 125622379 569078874 442586570 699395955
stdout
copy 
8678728751
https://ideone.com/MKndH7
language:
C++ (gcc 8.3)
created:
8 hours 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!