SHARE
TWEET

Untitled

a guest Apr 21st, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top