Subtask 1: ~N \le 1000~

Ở subtask này, do ~N~ khá nhỏ, nên ta có thể sinh ra toàn bộ tổng của các đoạn con liên tiếp, cho vào một mảng, sắp xếp mảng đó lại, và lấy ra kết quả tương ứng.

Subtask 2: ~N \le 10^5~

Để giải bài toán này, một hướng tiếp cận mà ta có thể nghĩ tới đó là kĩ thuật tìm kiếm nhị phân. Cụ thể, định nghĩa hàm ~f(x)~ là số lượng đoạn con liên tiếp trong mảng ~A~ có tổng lớn hơn hoặc bằng ~x~. Khi đó, dễ dàng nhận thấy f(x) là một mảng giảm đơn điệu, khi x tăng thì f(x) giảm. Do đó, ta có thể sử dụng kĩ thuật tìm kiếm nhị phân, để tìm giá trị ~x~ lớn nhất, sao cho ~f(x) \ge k~. Khi đó, x chính là kết quả cần tìm của ta.

Vậy nên giờ ta có thể chuyển về bài toán sau: Cho mảng ~A~ và một số nguyên ~x~, đếm xem có bao nhiêu đoạn con liên tiếp có tổng lớn hơn hoặc bằng ~x~. Với những bài liên quan tới tổng của một đoạn con liên tiếp, chúng ta có thể nghĩ tới kĩ thuật tổng tiền tố. Gọi ~pSum(i)~ là tổng tiền tố từ phần tử ~1~ đến ~i~, khi đó, ta cần đếm số lượng đoạn (L, R] trong mảng ban đầu, sao cho:

~pSum(R) - psum(L) \ge x~

~\Leftrightarrow psum(R) - x \ge psum(L)~

Đến đây, chúng ta có thể sử dụng các cấu trúc dữ liệu khác nhau như Fenwick Tree, Segment Tree, ... để giải bài toán trên.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;
int k;
int a[200001], psum[200001];

int BIT[200001];

void update(int x) {
    for (; x <= n; x += x & (-x))
        BIT[x]++;
}

int query(int x) {
    int ans = 0;
    for (; x > 0; x -= x & (-x))
        ans += BIT[x];
    return ans; 
}


bool check(int x) {
    for (int i = 1; i <= n; i++) BIT[i] = 0;
    int cnt = 0, cur = 0;
    for (int i = 1; i <= n; i++) {
        update(lower_bound(psum + 1, psum + 1 + n, cur) - psum);
        cur += a[i];
        cnt += query(upper_bound(psum + 1, psum + 1 + n, cur - x) - psum - 1);
    }   
    return (cnt >= k);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        psum[i] = a[i - 1] + psum[i - 1];
    }
    sort(psum + 1, psum + 1 + n);

    int l = -1e14, r = 1e14, ans = 0;

    while (l <= r) {
        int mi = (l + r) / 2;
        if (check(mi)) {
            ans = mi;
            l = mi + 1;
        }
        else
            r = mi - 1;
    }
    cout << ans;    
}