owo.c

#include <algorithm>
#include <iostream>
using namespace std;

struct activity {
    int no, start, end, val;
};

bool cmpAct(activity a, activity b)
{
    if (a.end == b.end)
        return a.val < b.val;
    else
        return (a.end < b.end);
}

bool cmpInt(int a, int b)
{
    return a < b;
}

int canSelect(activity arr[], int i)
{
    for (int j = i - 1; j >= 0; j--) {
        if (arr[j].end <= arr[i].start)
            return j;
    }
    return -1;
}

int counter = 0;

void answer(int ans[], activity arr[], int path[], bool flag[], int i, int idx)
{
    if (flag[i]){
        ans[idx] = arr[i].no;
        ++counter;
    }
    if (i != path[i]) {
        answer(ans, arr, path, flag, path[i], idx + flag[i]);
    }
    return;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int k;
        cin >> k;
        activity arr[k];

        for (int i = 0; i < k; i++)
            cin >> arr[i].no >> arr[i].start >> arr[i].end >> arr[i].val;

        sort(arr, arr + k, cmpAct);

        // for (int i = 0; i < k; i++)
        //     cout << arr[i].no << ", ";
        // cout << endl;

        int dp[k], path[k];
        bool flag[k];
        path[0] = 0;
        dp[0] = arr[0].val;
        flag[0] = true;

        for (int i = 1; i < k; i++) {
            int value = arr[i].val;
            int idx = canSelect(arr, i);
            if (idx >= 0)
                value += dp[idx];
            if (value > dp[i - 1]) {
                dp[i] = value;
                if (idx >= 0)
                    path[i] = idx;
                else
                    path[i] = i;
                flag[i] = true;
            } else {
                dp[i] = dp[i - 1];
                path[i] = i - 1;
                flag[i] = false;
            }
        }

        // for (int i = 0; i < k; i++)
        //     cout << dp[i] << ", ";
        // cout << endl;

        // for (int i = 0; i < k; i++)
        //     cout << path[i] << ", ";
        // cout << endl;

        // for (int i = 0; i < k; i++)
        //     cout << flag[i] << ", ";
        // cout << endl;

        int ans[k];
        counter = 0;
        answer(ans, arr, path, flag, k - 1, 0);
        sort(ans, ans + counter, cmpInt);
        int maxValue = dp[k - 1];
        cout << maxValue << endl;
        for (int i = 0; i < counter; i++)
            cout << ans[i] << (i != counter - 1 ? ' ' : '\n');
    }
}