记录编号	214603	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	2124.[HZOI 2015] Seq	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	2.926 s
提交时间	2015-12-16 20:50:25	内存使用	2.21 MiB

#define MAXN 500010UL
#define INF 0x3fffffffL
 
#include <cstdio>
#include <cstdlib>
 
struct Node{
	Node *left,*right;
	int fix,val,siz;
	Node(){
		siz=1;
		fix=rand();
		left=NULL,right=NULL;
		return;
	}
}*root;
 
int n,k,s[MAXN];
 
inline void Update(Node *&p){
	p->siz=1;
	if(p->left!=NULL) p->siz+=p->left->siz;
	if(p->right!=NULL) p->siz+=p->right->siz;
	return;
}
 
inline void Lturn(Node *&a){
	Node *b=a->right;
	a->right=b->left;
	b->left=a;
	a=b;Update(b->left);
	return;
}
 
inline void Rturn(Node *&a){
	Node *b=a->left;
	a->left=b->right;
	b->right=a;
	a=b;Update(b->right);
	return;
}
 
inline void Insert(Node *&p,int val){
	if(p==NULL){
		p=new Node();
		p->val=val;
		return;
	}
	else if(val<=p->val){
		Insert(p->left,val);
		if(p->left->fix<p->fix) Rturn(p);
	}
	else{
		Insert(p->right,val);
		if(p->right->fix<p->fix) Lturn(p);
	}
	Update(p);
	return;
}
 
inline int Find(Node *p,int val){
	if(p==NULL) return 0L;
	if(val>p->val){
		int temp=1+Find(p->right,val);
		if(p->left!=NULL) temp+=p->left->siz;
		return temp;
	}
	else return Find(p->left,val);
}
 
inline bool Check(int val){
	root=NULL;
	int Ans=1;
	for(int i=0;i<=n;i++){
		Ans+=Find(root,s[i]);
		Insert(root,val+s[i]);
	}
	return Ans<=k;
}
 
int main(){
	freopen("final_set.in","r",stdin);
	freopen("final_set.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1,t;i<=n;i++) scanf("%d",&t),s[i]=s[i-1]+t;
	int l=-INF,r=INF,mid,Ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(Check(mid)) Ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d",Ans);
	return 0;
}