fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mod 20011
  3. #define ninf -2000000
  4. using namespace std;
  5. typedef long long int ll;
  6. ll a[3010],dp1[3010],dp2[3010];
  7. ll n,k;
  8. ll rec2(ll w){
  9.     if(w<k-1)return ninf;
  10.     if(dp2[w]==ninf)
  11.         return dp2[w] = max(a[w]+rec2(w-1),max(a[w]+rec2(w-2),rec2(w-1)));
  12.     return dp2[w];
  13.  
  14. }
  15. ll rec(ll i)
  16. {
  17.  
  18.     if(i<0)return ninf;
  19.     if(dp1[i]!=ninf)return dp1[i];
  20.     else return dp1[i] = max(a[i] + rec(i-1),max(a[i]+rec(i-2),rec(i-1)));
  21. }
  22. int main()
  23. {
  24.     for(ll i=0;i<3010;i++)dp1[i]=dp2[i] = ninf;
  25.  
  26.     cin>>n>>k;
  27.     for(ll i=0;i<n;i++)cin>>a[i];
  28.  
  29.     dp1[0] = a[0];
  30.     rec(n-1);
  31.     dp2[k-1] = 0;
  32.     rec2(n-1);
  33.    // for(ll i=0;i<n;i++)cout<<" "<<dp1[i];
  34.    // cout<<endl;
  35.   //   for(ll i=k;i<n;i++)cout<<" "<<dp2[i]-a[i];
  36.    //  cout<<endl;
  37.     ll ans=ninf;
  38.     for(ll i=k;i<n;i++)
  39.         ans = max(ans,dp1[i]+dp2[i]-a[i]);
  40.     cout<<ans<<endl;
  41.     return 0;
  42. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
5 2
5 3 -2 1 1
stdout
copy 
11
https://ideone.com/a7UyoX
language:
C++14 (gcc 8.3)
created:
8 years 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!