[BZOJ 151]種樹
1735 ワード
同1150
毎回最大を取り、val[l]+val[r]-val[now]をスタックに入れます.
毎回最大を取り、val[l]+val[r]-val[now]をスタックに入れます.
/**************************************************************
Problem: 2151
User: momoka
Language: C++
Result: Accepted
Time:404 ms
Memory:6432 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;++i)
#define drep(i,t,s) for(int i=t;i>=s;--i)
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
char ch=getchar();
int f=1,x=0;
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;
}
int n,m,val[200500],l[200500],r[200500],ans;
bool mark[200500];
typedef pair<int,int>ele;
priority_queue<ele>q;
int main(){
//freopen("xx.in","r",stdin);
//freopen("xx.out","w",stdout);
n=read(); m=read();
if (m>(n>>1)){ puts("Error!"); return 0; }
rep(i,1,n){
val[i]=read();
q.push(make_pair(val[i],i));
l[i]=i-1;
r[i]=i+1;
}
l[1]=n; r[n]=1;
rep(i,1,m){
while (mark[q.top().second]) q.pop();
ele now=q.top();
int id=now.second;
q.pop();
ans+=now.first;
int ls=l[id],rs=r[id];
mark[ls]=1,mark[rs]=1;
l[id]=l[ls]; r[l[id]]=id;
r[id]=r[rs]; l[r[id]]=id;
val[id]=val[ls]+val[rs]-now.first;
q.push(make_pair(val[id],id));
}
printf("%d
",ans);
// getchar(); getchar();
//fclose(stdin); fclose(stdout);
return 0;
}