记录编号	585681	评测结果	TTTTTTTTTTTTTT
题目名称	Naptime	最终得分	0
用户昵称	在大街上倒立游泳	是否通过	未通过
代码语言	C++	运行时间	14.000 s
提交时间	2023-12-21 18:43:47	内存使用	5.78 MiB

#include<bits/stdc++.h>
using namespace std;
int f[3602][2],n,b,u[3688],ans=0;
inline int read()
{
	int k=0,f=1;
    char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c&15);
	return k*f;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main(){
    freopen("shihuai.in","r",stdin);
    freopen("shihuai.out","w",stdout);
    memset(f,0xcf,sizeof(f));
    n=read();
    b=read();
    for(int i=1;i<=n;i++) u[i]=read();
    f[0][0]=0;
    f[1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=b;j;j--){
            f[j][0]=max(f[j][0],f[j][1]);
            f[j][1]=max(f[j-1][0],f[j-1][1]+u[i]);
            //cout<<i<<' '<<j<<' '<<0<<' '<<f[i][j][0]<<endl;
            //cout<<i<<' '<<j<<' '<<1<<' '<<f[i][j][1]<<endl;
        }
    }
    ans=max(f[b][0],f[b][1]);
    //write(ans);
    memset(f,0xcf,sizeof(f));
    //f[0][0]=0;
    f[1][1]=u[1];
    for(int i=2;i<=n;i++){
        for(int j=b;j;j--){
            f[j][0]=max(f[j][0],f[j][1]);
            f[j][1]=max(f[j-1][0],f[j-1][1]+u[i]);
        }
    }
    ans=max(ans,f[b][1]);
    write(ans);
    return 0;
}