超级钢琴写了三个小时。
然后光顾着调题啥也没干。
唐了,交了几遍都只拿了十分,把每个部分检查完后发现原来是DP数组开小了? ? ?
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500010;
inline int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
struct node
{
int i,l,r,v,w;
bool operator< (const node & a) const
{
return v<a.v;
}
};
int n,m,l,r,sa[N],a[N];
int ans;
inline int Max(int x, int y)
{
return sa[x]>sa[y] ? x:y;
}
int log1[N],dp[N][20];
void st()
{
log1[0]=-1;
for (int i=1; i<=n; i++)
if (i&(i-1)) log1[i]=log1[i-1];
else log1[i]=log1[i-1]+1;
for (int i=1; i<=n; i++) dp[i][0]=i;
for (int j=1; (1<<j)<=n; j++)
for (int i=1;i+(1<<j)-1<=n;i++)
dp[i][j]=Max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
inline int rmq(int l,int r)
{
int tmp=log1[r-l+1];
return Max(dp[l][tmp],dp[r-(1<<tmp)+1][tmp]);
}
priority_queue <node> q;
signed main()
{
n=read(),m=read(),l=read(),r=read();
for(int i=1;i<=n;++i)
a[i]=read(),sa[i]=sa[i-1]+a[i];
st();
for(int i=1;i<=n;++i)
if(i+l-1<=n)
{
int ls=i+l-1,rs=min(i+r-1,n),pos=rmq(ls,rs),val=sa[pos]-sa[i-1];
q.push((node){i,ls,rs,val,pos});
}
else break;
while (!q.empty() && m)
{
node now=q.top(); q.pop();
ans+=now.v; m--;
node ls=now,rs=now;
ls.r=now.w-1;
if (ls.r>=ls.l)
ls.w=rmq(ls.l,ls.r),ls.v=sa[ls.w]-sa[ls.i-1],q.push(ls);
rs.l=now.w+1;
if (rs.r>=rs.l)
rs.w=rmq(rs.l,rs.r),rs.v=sa[rs.w]-sa[rs.i-1],q.push(rs);
}
cout<<ans<<endl;
}