AcWing 3493. 最大的和 两个前缀和的O(n) 做法
原题链接
简单
作者:
辉小歌
,
2021-05-24 22:18:20
,
所有人可见
,
阅读 245
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
long long int s[N];//默认全选的前缀和
long long int ss[N];//按照题目给的求前缀和
int n,k;
long long int ans=0;
int main(void)
{
int n,k; cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
int x;
for(int i=1;i<=n;i++)
{
cin>>b[i];
if(b[i]) ss[i]=ss[i-1]+a[i];
else ss[i]=ss[i-1];
}
for(int i=1;i<=n-k+1;i++)
{
long long int temp=s[i+k-1]-s[i-1];
temp+=ss[i-1]+ss[n]-ss[i+k-1];
if(temp>ans) ans=temp;
}
cout<<ans<<endl;
return 0;
}
我觉得这种简单易懂