fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int getNewSum(vector<int>a,int n,int block){
  4. 	unordered_map<int,int>b;
  5. 	b[block]++;
  6. 	vector<int>dp(n,0);
  7. 	dp[0]=a[0];   //first index is not block
  8. 	if(b[a[1]]==0){
  9. 		dp[1]=dp[0]+a[1];
  10. 	}
  11. 	if(b[a[2]]==0){
  12. 		dp[2]=max(dp[1]+a[2],dp[0]+a[2]);
  13. 	}
  14. 	for(int i=3;i<n;i++){
  15. 		if(b[a[i]]!=0){
  16. 			continue;
  17. 		}
  18. 		if(b[a[i-1]]==0){
  19. 			dp[i]=dp[i-1]+a[i];
  20. 		}
  21. 		if(b[a[i-2]]==0){
  22. 			dp[i]=max(dp[i-2]+a[i],dp[i]);
  23. 		}
  24. 		if(b[a[i-3]]==0){
  25. 			dp[i]=max(dp[i-3]+a[i],dp[i]);
  26. 		}
  27.  
  28. 	}
  29. 	return dp[n-1];
  30. }
  31.  
  32. int main() {
  33. 	// your code goes here
  34. 	vector<int>arr={1,2,3,4,5};
  35. 	int block=3;        //there can be list of blocks
  36. 	int n=arr.size();
  37. 	cout<<"The maximum sum after placing blocks is:"<<getNewSum(arr,n,block);
  38.  
  39. 	return 0;
  40. }
Success #stdin #stdout 0.01s 5260KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The maximum sum after placing blocks is:12
https://ideone.com/J4erPf
language:
C++ (gcc 8.3)
created:
3 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!