神奇的贪心
从大到小取$a_{i}$
因此对于每个，若最终答案不包含，则一定包含
于是每次取时，加入，允许撤销操作1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
const int N=500050;
int n,m,w[N],L[N],R[N],used[N];
struct node {LL val;int id;};
struct cmp {bool operator ()(node a,node b) {return a.val<b.val;}};
priority_queue<node,vector<node>,cmp> Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) w[i]=read(),Q.push((node){w[i],i});
for(int i=1;i<=n;i++) L[i]=i-1,R[i]=i+1;
R[0]=1,L[n+1]=n;LL ans=0;
while (m--)
{
while (used[Q.top().id]) Q.pop();
int k=Q.top().id;
used[L[k]]=used[R[k]]=1;
if (Q.top().val<=0) break;
ans=ans+Q.top().val,Q.pop();
Q.push((node){w[k]=w[L[k]]+w[R[k]]-w[k],k});
L[k]=L[L[k]],R[L[k]]=k;
R[k]=R[R[k]],L[R[k]]=k;
}
printf("%lld",ans);
return 0;
}