fork 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][j+m],dp[1][j]+data[i]);
  22. 		}	
  23. 		for(int j=0;j<=i;j++){
  24. 			dp[0][i+m]=max(dp[0][i+m],dp[0][j]+data[i]);
  25.  
  26. 			dp[1][i]=max(dp[1][i],dp[0][j]+data[i]);
  27. 		}
  28.  
  29. 		for(int j=0;j<2;j++){
  30. 			dp[j][i+1]=max(dp[j][i+1],dp[j][i]);
  31. 		}
  32.  
  33.  
  34. 		for(int j=0;j<13;j++){
  35. 			cout<<j<<"("<<dp[0][j]<<" "<<dp[1][j]<<")";
  36. 		}
  37. 		cout<<endl;
  38. 	}
  39. 	long long int ans=0;
  40. 	for(int i=0;i<2*n+3;i++){
  41. 		for(int j=0;j<2;j++){
  42. 			ans=max(ans,dp[j][i]);
  43. 		}
  44. 	}
  45. 	cout<<ans<<endl;
  46. 	return 0;
  47. }
Success #stdin #stdout 0.01s 5288KB
comments ()
stdin
copy 
12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728
stdout
copy 
0(0 864814169)1(0 864814169)2(0 0)3(0 0)4(0 0)5(864814169 864814169)6(0 0)7(0 0)8(0 0)9(0 0)10(0 0)11(0 0)12(0 0)
0(0 864814169)1(0 864814169)2(0 864814169)3(0 0)4(0 0)5(864814169 1581452546)6(1581452546 1581452546)7(0 0)8(0 0)9(0 0)10(0 0)11(0 0)12(0 0)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 0)5(864814169 1791703352)6(1581452546 1791703352)7(1791703352 1791703352)8(0 0)9(0 0)10(0 0)11(0 0)12(0 0)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 1791703352)7(1791703352 1818358009)8(1818358009 1818358009)9(0 0)10(0 0)11(0 0)12(0 0)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 1791703352)7(1791703352 1818358009)8(1818358009 1818358009)9(1144027534 1144027534)10(0 0)11(0 0)12(0 0)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 1791703352)7(1791703352 1818861580)8(1818358009 1818861580)9(1144027534 1818861580)10(2683675749 2683675749)11(0 0)12(0 0)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 2085824462)7(1791703352 2085824462)8(1818358009 1818861580)9(1144027534 1818861580)10(2683675749 2683675749)11(2296075268 2296075268)12(0 0)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 2085824462)7(1791703352 2469863347)8(1818358009 2469863347)9(1144027534 1818861580)10(2683675749 2683675749)11(2296075268 2763984457)12(2763984457 2763984457)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 2085824462)7(1791703352 2469863347)8(1818358009 2469863347)9(1818358009 2469863347)10(2683675749 2683675749)11(2296075268 2763984457)12(2763984457 2905341951)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 2085824462)7(1791703352 2469863347)8(1818358009 2469863347)9(1818358009 2469863347)10(2683675749 2683675749)11(2296075268 2763984457)12(2763984457 2905341951)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 2085824462)7(1791703352 2469863347)8(1818358009 2469863347)9(1818358009 2469863347)10(2683675749 3444498590)11(2683675749 3444498590)12(2763984457 3230686188)
0(0 864814169)1(0 864814169)2(0 926889183)3(0 926889183)4(0 926889183)5(864814169 1791703352)6(1581452546 2085824462)7(1791703352 2469863347)8(1818358009 2469863347)9(1818358009 2469863347)10(2683675749 3444498590)11(2683675749 3444498590)12(2763984457 3444498590)
4133001318
https://ideone.com/RE6J2k
language:
C++ (gcc 8.3)
created:
10 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!