p1714 切蛋糕 双指针+递推 80救命(玄关)
  • 板块学术版
  • 楼主guoshi
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/23 22:06
  • 上次更新2023/11/2 11:38:45
查看原帖
p1714 切蛋糕 双指针+递推 80救命(玄关)
945842
guoshi楼主2023/10/23 22:06
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N];
int l=1,r=0;//已取区间的端点 
long long sum,ans=-LONG_LONG_MAX;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++){
		if(sum+a[i]>a[i]){//不取等,只取一个更优 
			sum+=a[i];
			r=i;//r++;
		}
		else{
			sum=a[i];
			l=r=i;
		}
		while(r-l+1>m){//超出限度
			sum-=a[l];
			l++;
			while(l<=r&&a[l]<=0)
				sum-=a[l],l++;
		}
		ans=max(ans,sum);
	}
	cout<<ans;
    return 0;
}
2023/10/23 22:06
加载中...