fork(10) download
  1. #include<stdio.h>
  2. #define INF -6e12
  3.  
  4. /*
  5. C. George and Job
  6. http://c...content-available-to-author-only...s.com/problemset/problem/467/C
  7. */
  8.  
  9. typedef long long int LL;
  10.  
  11. int n,m;
  12.  
  13. LL sum[5005];
  14. LL arr[5005];
  15. LL memo[5005][5005];
  16. char calculated[5005][5005];
  17.  
  18. LL MAX(LL a,LL b)
  19. {
  20. return a > b ? a : b;
  21. }
  22.  
  23. LL dp(int index,int k)
  24. {
  25. // Meaning that we have crossed the array boundary but we still have some
  26. // m sized ranges to consider.
  27. if(index > n-m && k > 0)
  28. return INF;
  29.  
  30. // All the k ranges have been considered for the sum. No need to recurse further.
  31. if(k == 0)
  32. return 0;
  33.  
  34. // If the result for this subproblem has already been calculated, then return the result
  35. if(calculated[index][k] == 1)
  36. return memo[index][k];
  37.  
  38. LL ans1,ans2;
  39.  
  40. // Do not consider the current range. Move on to the next one
  41. ans1=dp(index+1,k);
  42.  
  43. // Consider the current range and recurse on the next non overlapping range.
  44. ans2=dp(index+m,k-1) + sum[index];
  45.  
  46. calculated[index][k]=1;
  47. memo[index][k]=MAX(ans1,ans2);
  48. return MAX(ans1,ans2);
  49. }
  50.  
  51. int main()
  52. {
  53. int i,k;
  54.  
  55. scanf("%d%d%d",&n,&m,&k);
  56.  
  57. for(i=0;i<n;i++)
  58. scanf("%ld",&arr[i]);
  59.  
  60. for(i=0;i<m;i++)
  61. sum[0]+=arr[i];
  62.  
  63. for(i=1;i<=(n-m);i++)
  64. {
  65. sum[i]=sum[i-1];
  66.  
  67. sum[i]-= arr[i-1];
  68. sum[i]+= arr[m+i-1];
  69. }
  70.  
  71. printf("%lld\n",dp(0,k));
  72.  
  73. return 0;
  74. }
Success #stdin #stdout 0s 222528KB
stdin
7 1 3
2 10 7 18 5 33 0
stdout
61