Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.64 KB | None | 0 0
  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4. int n,m,k,a[100005],i;
  5. int mem[100005][105];
  6. int qsum(int x,int y){
  7. return a[y] - a[x-1];
  8. }
  9. int luxu(int pos,int hotel){
  10. if(pos==n+1||hotel==m) return 0;
  11. if(hotel > m) return mem[pos][hotel] = -1e9;
  12. if(mem[pos][hotel]) return mem[pos][hotel];
  13. for(int i=pos;i<=n;i++){
  14. mem[pos][hotel] = max(mem[pos][hotel],qsum(i,i+k-1)+luxu(i+k,hotel+1));
  15. // printf("mem[%d][%d] = %d : i = %d\n",pos,hotel,mem[pos][hotel],i);
  16. }
  17. return mem[pos][hotel];
  18. }
  19. int main(){
  20. scanf("%d%d%d",&n,&m,&k);
  21. for(i=1;i<=n;i++){
  22. scanf("%d",&a[i]),a[i]+=a[i-1];
  23. }
  24. printf("%d",luxu(1,0));
  25. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement