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

#define MAXN 500010UL
#define INF 0x5fffffff

#define ll long long

#include <cstdio>
#include <cstdlib>
 
struct Node{
	Node *left,*right;
	ll fix,val,siz;
	Node(){
		siz=1;
		fix=rand();
		left=NULL,right=NULL;
		return;
	}
}*root;
 
ll 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,ll 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 ll Find(Node *p,ll val){
	if(p==NULL) return 0L;
	if(val>p->val){
		ll 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(ll val){
	root=NULL;
	ll Ans=1;
	for(ll i=0;i<=n;i++){
		Ans+=Find(root,s[i]);
		Insert(root,val+s[i]);
	}
	return Ans<=k;
}

inline ll in(){
	ll 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;
}

int main(){
	freopen("final_set.in","r",stdin);
	freopen("final_set.out","w",stdout);
	n=in(),k=in();
	for(ll i=1;i<=n;i++) s[i]=s[i-1]+in();
	ll 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("%lld",Ans);
	return 0;
}