fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17. #define MAX 100005
  18.  
  19. int n,m;
  20. ll a[MAX],f[2][205][2];
  21.  
  22. int main()
  23. {
  24.     fastio
  25.     #ifndef ONLINE_JUDGE
  26.     freopen(FILE ".inp","r",stdin);
  27.     freopen(FILE ".out","w",stdout);
  28.     #endif // ONLINE_JUDGE
  29.  
  30.      cin>>n>>m; foru(i,1,n)cin>>a[i];
  31.      f[1][m-1][1]=a[1];
  32.      foru(i,2,n)
  33.      {
  34.         int now=i%2,pre=1-now;
  35.         memset(f[now],0,sizeof(f[now]));
  36.         foru(j,0,m)
  37.         {
  38.             if(j>0)
  39.             {
  40.                 //f[i][j][0]=max(f[i][j][0],max(f[i][j-1][1],f[i-1][j-1][0]));
  41.                 f[now][j][0]=max(f[pre][j-1][1],f[pre][j-1][0]);
  42.                 if(j==m) f[now][j][0]=max(f[now][j][0],f[pre][j][0]);
  43.             }
  44.             if(j<m)
  45.             {
  46.                 f[now][j][1]=f[pre][j+1][1]+a[i];
  47.                 if(j==m-1) f[now][j][1]=max(f[now][j][1],f[pre][j+1][0]+a[i]);
  48.             }
  49.         }
  50.      }
  51.      cout<<f[n&1][m][0];
  52.  
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Disedm
language:
C++14 (gcc 8.3)
created:
5 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!