ÖÖÊ÷[¶Ñ][Ì°ÐÄ][Á´±í]

´«ËÍÃÅ

---

#include<bits/stdc++.h>
#define N 200050
using namespace std;
int n,m,a[N],l[N],r[N],flag[N],ans;
struct Node{
 int x,val;
 bool operator < (const Node &a) const{
  return a.val > val;
 }
};
priority_queue<Node> q;
void Delete(int x){flag[x]=1 , l[r[x]]=l[x] , r[l[x]]=r[x];}
int main(){
 scanf("%d%d",&n,&m); if(m>n/2){printf("Error!"); return 0;}
 for(int i=1;i<=n;i++){
  scanf("%d",&a[i]); q.push(Node{i,a[i]});
  l[i]=i-1 , r[i]=i+1;
 }l[1]=n , r[n]=1;
 for(int i=1;i<=m;i++){
  while(!q.empty() && flag[q.top().x]) q.pop();
  Node X = q.top(); q.pop();
  ans += X.val; int L=l[X.x] , R=r[X.x];
  a[X.x]=a[L]+a[R]-X.val;
  q.push(Node{X.x,a[X.x]}); 
  Delete(L) , Delete(R);
 }printf("%d",ans); return 0;
}