Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;

struct fenwickTree{
  long long f[maxn];

  fenwickTree() {
    memset(f, 0, sizeof f);
  }

  void upd(int i, long long x) {
    ++i;
    for(; i < maxn; i += i & -i) f[i] += x;
  }

  long long get(int i) {
    ++i;
    long long ans = 0;
    for(; i > 0; i -= i & -i) ans += f[i];
    return ans;
  }

  void clear() {
    memset(f, 0, sizeof f);
  }
}fw1, fw2;

int n, k;
int a[maxn];
int s[maxn];
vector<int> num;

pair<long long, long long> solve(int val) {
  /// s[r] - s[l - 1] >= val -> s[l-1] <= s[r] - val
  fw1.clear();
  fw2.clear();
  long long cnt = 0, sum = 0;
  for(int i = 1; i <= n; ++i) {
    int id = lower_bound(num.begin(), num.end(), s[i - 1]) - num.begin();
    fw1.upd(id, 1);
    fw2.upd(id, s[i - 1]);

    id = upper_bound(num.begin(), num.end(), s[i] - val) - num.begin();

    if (id > 0) {
      --id;
      long long _cnt = fw1.get(id);
      long long _sum = fw2.get(id);
      sum -= _sum;
      sum += 1LL * s[i] * _cnt;
      cnt += _cnt;
    }
  }
  return make_pair(cnt, sum);
} 

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);

  freopen("signal.inp", "r", stdin);
  freopen("signal.out", "w", stdout);

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

  for(int i = 0; i <= n; ++i) num.push_back(s[i]);
  sort(num.begin(), num.end());

  int low = -2e8, high = 2e8, ans = low;
  while(low <= high) {
    int mid = (low + high) >> 1;
    auto foo = solve(mid);
    if (foo.first >= k) {
      ans = mid;
      low = mid + 1;
    }
    else {
      high = mid - 1;
    }
  }

  auto res = solve(ans);

  cout << res.second - (res.first - k) * ans << "\n";

  return 0;
}