Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
98080 | xujindong | 早凉与序列4 | C++ | 解答错误 | 60 | 358 MS | 2992 KB | 934 | 2023-08-14 11:58:59 |
#include<bits/stdc++.h> using namespace std; int n,k,lg[100005]; long long x,a[100005],sum1[100005],sum2[100005],st1[100005][20],st2[100005][20],ans; long long query(int l,int r,long long st[100005][20]){ return l>r?-0x3f3f3f3f3f3f3f3f:max(st[l][lg[r-l+1]],st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); } int main(){ cin>>n>>k>>x; if(x<0)x=-x,k=n-k; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]+a[i]+x,sum2[i]=sum2[i-1]+a[i]-x; for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++)st1[i][0]=sum1[i],st2[i][0]=sum2[i]; for(int j=1;1<<j<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)st1[i][j]=max(st1[i][j-1],st1[i+(1<<(j-1))][j-1]),st2[i][j]=max(st2[i][j-1],st2[i+(1<<(j-1))][j-1]); for(int i=1;i<=n;i++){ if(i+k-1<n)ans=max(ans,max(query(i,i+k-1,st1)-sum1[i-1],query(i+k,n,st2)+2*k*x-sum2[i-1])); else ans=max(ans,query(i,n,st1)-sum1[i-1]); } return cout<<ans<<'\n',0; }