## Editorial for Bedao Grand Contest 09 - SIGNAL

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

#### 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;
}