fork(3) download 
  1. #include <iostream>
  2. #include<algorithm>
  3. #include<stdio.h>
  4. using namespace std;
  5.  
  6. typedef long long int ll;
  7. ll dp[5005][5005];
  8. ll sum[5005];
  9.  
  10. int main() {
  11.     // your code goes here
  12.     ll n,m,k,i,j,size,ki;
  13.     cin>>n>>m>>ki;
  14.     size=m;
  15.  
  16.     ll a[n+2];
  17.  
  18.      if(m==1)
  19.      {
  20.      	for(i=0;i<n;i++)
  21.          cin>>a[i];
  22.  
  23.          sort(a,a+n);
  24.          if(ki==1){
  25.          cout<<a[n-1]<<endl;
  26.          return 0;
  27.         }
  28.        // sort(a,a+n);
  29.         ll s=0;
  30.         //a[0]=0;
  31.         //for(i=n;i>=n-ki+1;i--)
  32.          //cout<<a[i]<<" ";
  33.  
  34.         for(i=n-1;i>=n-ki;i--)
  35.          s+=a[i];
  36.  
  37.          cout<<s<<endl;
  38.          return 0;
  39.      }
  40.  
  41.      for(i=1;i<=n;i++)
  42.      cin>>a[i];
  43.  
  44.      for(i=1;i<size;i++)
  45.       sum[i]=a[i];
  46.  
  47.      for(i=1;i<=size;i++)
  48.       {
  49.       	sum[size]+=a[i];
  50.       }
  51.  
  52.     //  cout<<sum[2]<<" ";
  53.  
  54.     for(i=size+1;i<=n;i++)
  55.     {
  56.         sum[i]+= sum[i-1]- a[i-size]+ a[i];
  57.      // cout<<sum[i]<<" ";
  58.     }
  59.    // cout<<endl;
  60.  
  61.     for(i=0;i<=5002;i++)
  62.     {
  63.         for(j=0;j<=5002;j++)
  64.          dp[i][j]=0;
  65.     }
  66.  
  67.     for(j=1;j<=n;j++)
  68.      dp[1][j]= max(sum[j], dp[1][j-1]);
  69.  
  70.     for(k=2;k<=ki;k++)
  71.     {
  72.         for(j=1;j<=n;j++)
  73.         {
  74.             if(j-size>=size)
  75.             dp[k][j]= max(dp[k-1][j-size]+sum[j],dp[k][j-1]);
  76.         }
  77.     }
  78.     /*
  79.     for(i=1;i<=ki;i++)
  80.     {
  81.         for(j=1;j<=n;j++)
  82.          cout<<dp[i][j]<<" ";
  83.          cout<<endl;
  84.     }
  85.     */
  86.     cout<<dp[ki][n]<<endl;
  87.     return 0;
  88. }
Success #stdin #stdout 0s 199040KB
comments (?)
stdin 
3 1 3
3 2 1
stdout 
6
https://ideone.com/2cC2Fb
language:
C++ (gcc 8.3)
created:
9 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!