fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int n,k;
  5. const int M = 1e9 + 7;
  6. int dp[1003][1003][2][2];
  7. int func(int i, int ct, vector<vector<int>>&v, int prev1, int prev2){
  8.   if(i == v.size()){
  9.      if(ct == k){
  10.         return 0;
  11.      }
  12.      else{
  13.         return -1e12;
  14.      }
  15.   }
  16.   if(dp[i][ct][prev1][prev2] != -1){
  17.     return dp[i][ct][prev1][prev2];
  18.   }
  19.   int val = -1e12;
  20.   val = max(val, func(i+1,ct,v,0,0));
  21.   if(prev1 == 0 && prev2 == 0){
  22.      val = max(val, max(func(i+1,ct+1,v,0,0) + v[i][0] + v[i][1],func(i+1,ct+1,v,0,0) + v[i][1] + v[i][2]));
  23.      if(i+1<v.size()){
  24.         val = max(val, func(i+1,ct+2,v,1,0) + v[i][0] + v[i+1][0] + v[i][1] + v[i][2]);
  25.         val = max(val, func(i+1,ct+2,v,0,1) + v[i][0] + v[i+1][2] + v[i][1] + v[i][2]);
  26.         val = max(val, func(i+1,ct+2,v,1,1) + v[i][0] + v[i+1][0] + v[i][2] + v[i+1][2]);
  27.         val = max(val, func(i+1,ct+1,v,1,0) + v[i][0] + v[i+1][0]);
  28.         val = max(val, func(i+1,ct+1,v,0,1) + v[i][2] + v[i+1][2]);
  29.      }
  30.   }
  31.   else if(prev1 == 1 && prev2 == 0){
  32.      val = max(val, func(i+1,ct+1,v,0,0) + v[i][1] + v[i][2]);
  33.      if(i+1<v.size()){
  34.         val = max(val, func(i+1,ct+1,v,0,1) + v[i][2] + v[i+1][2]);
  35.      }
  36.   }
  37.   else if(prev1 == 0 && prev2 == 1){
  38.        val = max(val, func(i+1,ct+1,v,0,0) + v[i][0] + v[i][1]);
  39.      if(i+1<v.size()){
  40.         val = max(val, func(i+1,ct+1,v,1,0) + v[i][0] + v[i+1][0]);
  41.      }
  42.   }
  43.   return dp[i][ct][prev1][prev2] = val;
  44. }
  45. void ans(){
  46.     cin>>n>>k;
  47.     vector<vector<int>>v(n,vector<int>(3));
  48.     for(int i = 0; i<n; ++i){
  49.         for(int j =0; j<3; ++j){
  50.             cin>>v[i][j];
  51.         }
  52.     }
  53.     memset(dp,-1,sizeof(dp));
  54.     cout<<func(0,0,v,0,0)<<"\n";
  55. }
  56. int32_t main(){
  57.     ans();
  58. }
Success #stdin #stdout 0.02s 34928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/J5lWPO
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!