1 条题解

  • 1
    @ 2023-7-30 15:39:13
    #include<iostream>
    #include<string>
    #include<cctype>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<iomanip>
    using namespace std;
    #define int long long
    const int N = 2e5+10;
    const int INF = 0x3f3f3f3f3f3f3f3f;
    int n,m,a[N],dp[N],q[N],num[N],sum=0;
    signed main(){
    	//freopen("","r",stdin);
    	//freopen("","w",stdout);
    	cin>>n>>m;
    	m++;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		sum+=a[i];
    	}
    	int l,r;
    	l=r=1,q[r++]=0;
    	for(int i=1;i<=n;i++){
    		while(l<r&&q[l]<=i-m-1)l++;
    		dp[i]=a[i]+num[l];
    		while(l<r&&num[r-1]>dp[i])r--;
    		num[r]=dp[i];
    		q[r++]=i;
    	}
    	int minn=INF;
    	for(int i=n;i>n-m;i--)minn=min(minn,dp[i]);
    	cout<<sum-minn<<endl;
    	return 0;
    }
    
    
    • 1

    信息

    ID
    2738
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    14
    已通过
    10
    上传者