fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. long long suml, sumr, n, res, k, fl, num, a[1000009], dp[1000009], f[2005][2005], g[2005][2005];
  4. bool ngcheck;
  5. void sub1()
  6. {
  7.     suml=0;
  8.     sumr=0;
  9.     ngcheck=false;
  10.     for(int i=1; i<=n; i++)
  11.     {
  12.         if(a[i]<0) ngcheck=true, num=a[i];
  13.         else
  14.         {
  15.             if(ngcheck==false) suml+=a[i];
  16.             if(ngcheck==true) sumr+=a[i];
  17.         }
  18.     }
  19.     if(k==1) cout << max(suml+sumr+num,max(suml,sumr));
  20.     else cout << suml+sumr;
  21. }
  22. void sub2()
  23. {
  24.     dp[0]=0;
  25.     res=-1e18;
  26.     for(int i=1; i<=n; i++)
  27.     {
  28.         dp[i]=max(dp[i-1]+a[i],a[i]);
  29.         res=max(res,dp[i]);
  30.     }
  31.     cout << res;
  32. }
  33. void sol()
  34. {
  35.     for(int i = 0; i <= n; i++) {
  36.         for(int j = 0; j <= k; j++) {
  37.             f[i][j] = -1e18;
  38.             g[i][j] = -1e18;
  39.         }
  40.     }
  41.     for(int i = 0; i <= n; i++)
  42.         f[i][0] = 0;
  43.     for(int j = 1; j <= k; j++) {
  44.         for(int i = 1; i <= n; i++) {
  45.             g[i][j] = max(g[i-1][j], f[i-1][j-1]) + a[i];
  46.             f[i][j] = max(f[i-1][j], g[i][j]);
  47.         }
  48.     }
  49.  
  50.     cout << f[n][k];
  51. }
  52. int main()
  53. {
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0);
  56.     cout.tie(0);
  57.     if(fopen("kd.inp","r"))
  58.     {
  59.         freopen("kd.inp","r",stdin);
  60.         freopen("kd.out","w",stdout);
  61.     }
  62.     cin >> n >> k;
  63.     fl=0;
  64.     for(int i=1; i<=n; i++)
  65.     {
  66.         cin >> a[i];
  67.         if(a[i]<0) fl++;
  68.     }
  69.     if(fl==1) sub1();
  70.     else if(k==1) sub2();
  71.     else sol();
  72.     return 0 ;
  73. }
  74.  
Success #stdin #stdout 0.01s 5628KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/13ydym
language:
C++14 (gcc 8.3)
created:
16 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!