Subtask 1: ~\sum n^3 \le 500^3~

Với giới hạn trên, ta sẽ sử dụng quy hoạch động, gọi ~DP[i][j]~ là số lượng cứ điểm có tổng sức mạnh ~\le S~ lớn nhất khi chia ~i~ đơn vị quân đầu tiên thành đúng ~j~ đoạn liên tiếp. Công thức truy hồi: $$DP[i][j] = \max_{0 \le x < i} \Big( DP[x][j - 1] + \big[ \text{sum}(x + 1 \dots i) \le S \big] \Big)$$ Trong đó biểu thức ~\big[ \text{sum} \dots \le S \big]~ trả về ~1~ nếu tổng đoạn từ ~x+1~ đến ~i~ không vượt quá ~S~, ngược lại trả về ~0~.

Subtask 2: ~\sum n \le 5 \cdot 10^5~

Ta xét 2 trường hợp tất cả:

Trường hợp 1: Không tồn tại phần tử ~a_i~ nào mà ~a_i > S~

Ta có một cách tham lam ở đây là giữ lại ~k - 1~ phần tử đơn lẻ làm ~k - 1~ đoạn (chắc chắn ~\le S~), và gộp tất cả các phần tử còn lại thành 1 đoạn tổng thể. Như vậy ta thấy được rằng đáp án chắc là tối thiểu ~K - 1~

Như vậy ta chỉ cần việc kiểm tra xem có cách để chia dãy mà có đáp án là ~K~, ở đây có nhiều cách. Một trong số đó là ta có thể đếm xem duyệt từ trái sang phải, tính cộng dồn tổng, nếu vượt ~S~ thì ngắt đoạn mới, và đếm xem có thể chia được bao nhiêu dãy tất cả.

Nếu số dãy tính được mà bé hơn hoặc bằng ~K~ thì đáp án sẽ là ~K~, còn không thì là ~K - 1~

Trường hợp 2: Có tồn tại phần tử ~a_i~ nào mà ~a_i > S~

Thay vì nghĩ theo hướng "cắt" mảng, ta hãy nghĩ theo hướng "gộp" các phần tử. Ban đầu, ta coi mỗi phần tử là một đoạn riêng biệt. Để có đúng ~k~ đoạn, ta cần thực hiện đúng ~n - k~ thao tác gộp hai đoạn kề nhau.

Với ~V~ là số lượng phần tử ban đầu có giá trị bé hơn hoặc bằng ~S~, mục tiêu của ta là giữ cho ~V~ giảm đi ít nhất có thể sau ~n - k~ lần gộp này. Quan sát với các phần tử lớn hơn ~S~:

• Nếu ta ghép những phần tử này với các phần tử nhỏ hơn liền kề thành một đoạn thì đáp án ~V~ sẽ giảm đi.

• Tuy nhiên nếu như ta có cách gộp các phần tử này với nhau thành một đoạn riêng biệt thì đáp án ~V~ sẽ giữ nguyên.

Hiển nhiên ý tưởng tham lam ở đây là sẽ ưu tiên gộp những phần tử lớn hơn ~S~ với nhau trước. Thực tế không phải lúc nào ta cũng có thể làm được như vậy, nên là ta sẽ đi tìm và ghép hai phần tử lớn hơn ~S~ mà khoảng cách giữa chúng là nhỏ nhất, với mục tiêu là phải giữ được nhiều phần tử nhỏ hơn ~S~ được nhiều nhất có thể.

Thuật toán tham lam sẽ như sau:

V = count of elements with a_i <= S
R = n - k
Find gaps d (count of elements <= S) between
consecutive elements > S, sort ascending
for each d in ascending order:
    if R >= d + 1:
        R = R - (d + 1)
        V = V - d
    else:
        break
V = V - R
return max(0, V)

Độ phức tạp sẽ là ~O(n \times log_2(n))~

// Hello I'm Nekan
//
#include <bits/stdc++.h>
#define Nekan "test"
#define fi first
#define se second
#define pb push_back
#define zs(v) ((int)(v).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define pii pair<int, int>

typedef long double ld;
typedef long long ll;

const int N = 1e5 + 5;
const long long mod = 1e9 + 7; /// 998244353

using namespace std;

void xuly() {
    int n, k, S;
    cin >> n >> k >> S;
    vector<int> a(n);

    bool is_second_case = false;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] > S) is_second_case = true;
    }

    auto solve_first = [&]() {
        int sum = 0, cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (sum + a[i] > S) {
                ++cnt;
                sum = 0;
            }
            sum += a[i];
        }

        cout << (cnt + 1 <= k ? k : k - 1) << '\n';
    };

    auto solve_second = [&]() {
        int pre = -1;
        vector<int> segments;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] <= S) {
                ++ans;
                continue;
            }
            if (pre != -1) segments.push_back(i - pre - 1);
            pre = i;
        }

        sort(segments.begin(), segments.end());

        for (int len : segments) {
            if (n - (len + 1) <= k) {
                int actual_merge = n - k;
                ans -= min(actual_merge, len); //in case n - k = len + 1
                n = k;
                break;
            }
            ans -= len;
            n -= len + 1;
        }

        cout << max(0, ans - (n - k)) << '\n';
    };

    if (!is_second_case) solve_first();
    else solve_second();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    if (fopen(Nekan ".inp", "r")) {
        freopen(Nekan ".inp", "r", stdin);
        freopen(Nekan ".out", "w", stdout);
    }
    int t; cin >> t;
    while(t--)
        xuly();
}

//Surely nothing could go wrong.