SPOJ ABA12E

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

ll arr[50001];
ll pre[50001];
ll n,k;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        pre[i] = pre[i-1] + arr[i];
    }
    /*ll mid = 15;
    ll after = 0;
    ll before = 0;
    for(int i = 1; i <= n; i++) {
        //before += lower_bound(pre+i,pre+n+1,mid+pre[i-1]) - (pre+i);
        after += (pre+n+1) - lower_bound(pre+i,pre+n+1,mid+pre[i-1]+1);
        before += upper_bound(pre+i,pre+n+1,mid+pre[i-1]-1)-(pre+i);
    }
    cout << "before is " << before << " after is " << after << "\n";*/
    ll low = *min_element(arr+1,arr+n+1);
    ll high = pre[n];
    ll possible = (n*(n+1))/2;
    while(low <= high) {
        ll mid = (high+low)/2;
        ll before = 0;
        ll after = 0;
        for(int i = 1; i <= n; i++) {
            //before += lower_bound(pre+i,pre+n+1,mid+pre[i-1]) - (pre+i);
            after += (pre+n+1) - lower_bound(pre+i,pre+n+1,mid+pre[i-1]+1);
            before += upper_bound(pre+i,pre+n+1,mid+pre[i-1]-1)-(pre+i);
        }
        ll times = possible - after - before;
        //cout << "before is " << before << " times is " << times << " at low = " << low << " high = " << high << " mid = " << mid << "\n";
        if(before+1 <= k && before+times >= k) {
            cout << mid << "\n";
            break;
        }
        else if(before+times < k) {
            low = mid+1;
        }
        else {
            high = mid-1;
        }
    }
    return 0;
}