fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.  
  8.     vector<int>h={4,1,1,5,6};
  9.     int n=h.size();
  10.     vector<vector<int>>dp(n,vector<int>(4,0));
  11.     dp[0][2]=0;
  12.     dp[0][3]=0;
  13.     dp[1][2]=h[0]+h[1];
  14.     dp[1][3]=0;
  15.     dp[2][2]=h[1]+h[2];
  16.     dp[2][3]=h[0]+h[1]+h[2];
  17.     int maxi=0;
  18.     for(int i=3;i<n;i++){
  19.  
  20.         int ans=0;
  21.         for(int j=i-3;j>=0;j--){
  22.             if(j==i-3){
  23.                 ans=max(ans,dp[j][2]);
  24.             }
  25.             else{
  26.             ans=max(ans,max(dp[j][2],dp[j][3]));
  27.             }
  28.         }        
  29.         dp[i][2]=h[i]+h[i-1]+ans;
  30.         int ans1=0;
  31.         for(int j=i-5;j>=0;j--){
  32.             ans1=max(ans1,max(dp[j][2],dp[j][3]));
  33.         }
  34.         dp[i][3]=h[i]+h[i-1]+h[i-2]+ans1;
  35.  
  36.         maxi=max(maxi,max(dp[i][2],dp[i][3]));
  37.  
  38.     }
  39.  
  40.     //cout<<max(dp[n-1][2],dp[n-1][3]); this is wrong because it is not necessary that largest sum will happen only when last robbed house is n-1 indexed or last hpuse.
  41.     //eg 1,5,5,5,1
  42.     cout<<maxi<<endl;
  43.     return 0;
  44. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
16
https://ideone.com/K6Clp1
language:
C++ (gcc 8.3)
created:
1 day 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!