记录编号	219092	评测结果	AAAAAAAAAAAAAAAAAAT
题目名称	[HZOI 2015] Seq	最终得分	94
用户昵称	stdafx.h	是否通过	未通过
代码语言	C++	运行时间	2.152 s
提交时间	2016-01-13 06:39:10	内存使用	8.32 MiB

#define ll long long

#define MAXN 100010UL
#define MAXS 20UL

#include <queue>
#include <stdio.h>

struct Point{
	int L,R,e,val;
	friend bool operator < (Point a,Point b){return a.val<b.val;}
};

std::priority_queue<Point> que;

int n,K,l,r,s[MAXN],t[MAXS][MAXN];
ll Ans;Point tmp;

inline int in(){
	int x=0,c=getchar();
	bool flag=false;
	while(c<'0'||c>'9'){
		if(c=='-') flag=true;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(flag) return -x;
	return x;
}

inline int Query(int l,int r){
	int len=r-l+1,k=0;
	while((1<<(k+1))<=len) k++;
	return s[t[k][l]]<s[t[k][r-(1<<k)+1]]?t[k][l]:t[k][r-(1<<k)+1];
}

int main(){
	freopen("final_set.in","r",stdin);
	freopen("final_set.out","w",stdout);
	n=in(),K=in();l=1,r=n;
	for(int i=1;i<=n;i++) s[i]=in()+s[i-1];
	for(int i=1;i<=n;i++) t[0][i]=i;
	for(int w=1,j=2,k=1,T=n+1;j<=T;w++,k<<=1,j<<=1) for(int i=0,R=n-j+1;i<=R;i++)
		t[w][i]=s[t[w-1][i]]<s[t[w-1][i+k]]?t[w-1][i]:t[w-1][i+k];
	for(int i=1,RangeL,RangeR;i<=n;i++){
		RangeL=i-r+1,RangeR=i-l+1;
		if(RangeL<1) RangeL=1;
		if(RangeR<0) continue;
		if(RangeL>RangeR) continue;
		que.push((Point){RangeL,RangeR,i,s[i]-s[Query(RangeL-1,RangeR-1)]});
	}
	for(int i=1,t;i<=K;i++){
		tmp=que.top();
		que.pop();
		Ans=tmp.val;
		t=Query(tmp.L-1,tmp.R-1)+1;
		if(tmp.L<t) que.push((Point){tmp.L,t-1,tmp.e,s[tmp.e]-s[Query(tmp.L-1,t-2)]});
		if(tmp.R>t) que.push((Point){t+1,tmp.R,tmp.e,s[tmp.e]-s[Query(t,tmp.R-1)]});
	}
	printf("%lld",Ans);
	return 0;
}