2021 Huazhong University of Science and Technology Freshmen Cup

2021 Huazhong University of Science and Technology Freshmen Cup - Solution

G. Awson Loves Chipmunks

Awson loves chipmunks, especially the $k$-th one among all $n$ chipmunks! He wants to keep a consecutive interval of chipmunks in his home, and the interval should include the $k$-th chipmunk.

However, chipmunks eat a lot and it is a heavy burden for Awson to buy food for all chipmunks. Specifically, the $i$-th chipmunk has a hunger value $a_i$. If Awson decides to raise the chipmunks from index $l$ to $r$ ($1 \le l \le k \le r \le n$), then the burden brought to Awson will be

$$f(l, r) = \sum_{i=l}^{r} a_i$$

Awson does not want to worry too much about chipmunks’ food, so he will choose the interval with the $m$-th smallest burden. Now you are required to tell Awson the burden he will carry.

Input

The first line contains three integers $n$ ($1 \le n \le 10^6$), $k$ ($1 \le k \le n$) and $m$ ($1 \le m \le k(n - k + 1)$) as described above.
The second line contains $n$ integers. The $i$-th integer $a_i$ ($|a_i| \le 10^9$) represents the hunger value of the $i$-th chipmunk.

Output

Print an integer representing the $m$-th smallest burden.

Scoring

The problem contains several subtasks. You can get the corresponding score for each passed test case.

• Subtask 1 (30 points): $n \le 10^3$.
• Subtask 2 (70 points): no additional constraints.

Examples

input
4 2 3
1 2 4 8
output
6

input
4 2 2
-1 2 -4 8
output
-2

Note

In the first example, the second chipmunk must be chosen, and there are 6 ways to choose the interval in total. They are $f(2, 2) = 2$, $f(1, 2) = 3$, $f(2, 3) = 6$, $f(1, 3) = 7$, $f(2, 4) = 14$, and $f(1, 4) = 15$. Among them, $f(2, 3) = 6$ is the third smallest, so the answer is 6.

思路

二分答案。
记和不超过 $x$ 的区间个数为$f(x)$。若 $f(x) \geq m$ 且$f(x-1) < m$,则答案为$x$

考虑如何快速计算 $f(x)$。预处理两个数组 $R = \sum_{k<j\leq i}a_j \ (i > k)$ 与
$L = \sum_{i\leq j\leq k}a_j \ (i \leq k)$,则每一个包含$k$的区间都可以表示成 $L$ 和 $R$ 中两个元素之和。

将两数组分别排序, 由于 $L$ 和 $R$ 均单调,可以用双指针,复杂度 $O(n \log W)$($W$ 为值域)

代码

#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
constexpr int N = 1e6 + 10;

i64 n, k, m, tmp, pl, pr, ans;
std::array<i64, N> a;
std::vector<i64>l, r;

int main () {
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    std::cin >> n >> k >> m;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    for (int i = k; i >= 1; --i) {
        tmp += a[i];
        l.push_back(tmp);
    }
    tmp = 0;
    for (int i = k; i <= n; ++i) {
        tmp += a[i];
        r.push_back(tmp);
    }
    std::sort(l.begin(), l.end());
    std::sort(r.begin(), r.end());
    i64 high = l.back() + r.back() - a[k];
    i64 low = l.front() + r.front() - a[k];
    ans = low;
    while (low <= high) {
        i64 mid = (low + high) >> 1;
        pr = r.size() - 1;
        i64 cnt = 0;
        for (pl = 0; pl < l.size(); ++pl) {
            while (pr >= 0 and l[pl] + r[pr] - a[k] > mid) {
                pr--;
            }
            cnt += pr + 1;
        }
        if (cnt >= m) {
            ans = mid;
            high = mid - 1;
        }else {
            low = mid + 1;
        }
    }
    std::cout << ans << '\n';
    return 0;
}