fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.  
  5.     vector<int>v={100,100,100};
  6.     int n=v.size();
  7.     int p=1;
  8.     int k=3;
  9.     //int dp[n][k+1][n+1]={INT_MIN}; only initializes first element.
  10.     vector<vector<vector<int>>>dp(n,vector<vector<int>>(k+1,vector<int>(n+1,INT_MIN)));
  11.     for(int i=0;i<n;i++){
  12.  
  13.             dp[i][0][0]=0;
  14.  
  15.     }
  16.     dp[0][1][0]=v[0];
  17.     dp[1][1][0]=max(v[0],v[1]);
  18.     dp[1][2][0]=INT_MIN;
  19.     dp[1][2][1]=v[0]+v[1]-p;
  20.  
  21.     for(int i=2;i<n;i++){
  22.         for(int j=1;j<=k;j++){
  23.             for(int c=0;c<=i;c++){
  24.                 dp[i][j][c]=max({dp[i-1][j][c],v[i]+dp[i-2][j-1][c],v[i]+v[i-1]-p+dp[i-2][j-2][c-1]});
  25.             }
  26.         }
  27.     }
  28.  
  29.     cout<<*max_element(dp[n-1][k].begin(),dp[n-1][k].end())<<endl;
  30.  
  31.     return 0;
  32. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
299
https://ideone.com/0PKu28
language:
C++ (gcc 8.3)
created:
14 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!