Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<stdio.h>
- using namespace std;
- int n,m,k,a[100005],i;
- int mem[100005][105];
- int qsum(int x,int y){
- return a[y] - a[x-1];
- }
- int luxu(int pos,int hotel){
- if(pos==n+1||hotel==m) return 0;
- if(hotel > m) return mem[pos][hotel] = -1e9;
- if(mem[pos][hotel]) return mem[pos][hotel];
- for(int i=pos;i<=n;i++){
- mem[pos][hotel] = max(mem[pos][hotel],qsum(i,i+k-1)+luxu(i+k,hotel+1));
- // printf("mem[%d][%d] = %d : i = %d\n",pos,hotel,mem[pos][hotel],i);
- }
- return mem[pos][hotel];
- }
- int main(){
- scanf("%d%d%d",&n,&m,&k);
- for(i=1;i<=n;i++){
- scanf("%d",&a[i]),a[i]+=a[i-1];
- }
- printf("%d",luxu(1,0));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement