Code : Time Travel

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();
    priority_queue<long long> heap;

    long long pref = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (pref - a[i] > 0) {
            heap.push(a[i]);
            pref -= a[i];
            ans++;
        } else {
            // Try swapping it with the biggest element chosen previously.
            if (!heap.empty() && heap.top() > a[i]) {
                auto old = heap.top();
                heap.pop();

                pref += 2 * old;
                pref -= a[i];
                heap.push(a[i]);
            } else {
                pref += a[i];
            }
        }
    }
    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int m_inf = -(int)1e5;

void solve(vector<int> &a) {
    int n = a.size();

    int sum = accumulate(a.begin(), a.end(), 0);
    vector<vector<int>> dp(n, vector<int>(sum + 1, m_inf));

    dp[0][a[0]] = 0;
    for (int i = 1; i < n; i++) {
        for (int pref = 1; pref <= sum; pref++) {
            int np = pref - a[i];
            if (np > 0) {
                dp[i][np] = max(dp[i][np], dp[i - 1][pref] + 1);
            }
            np = pref + a[i];
            if (np <= sum) {
                dp[i][np] = max(dp[i][np], dp[i - 1][pref]);
            }
        }
    }

    int ans = -1;
    for (int s = 0; s <= sum; s++) {
        ans = max(ans, dp[n - 1][s]);
    }
    cout << ans << endl;
}

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

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}