K. Competitions

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

typedef long long ll;
typedef vector< ll > vl;

vector< vl > dp;
vector< vl > v;
int n;

inline bool cmp(const vl &a ,const vl &b)
{
    return a[0] < b[0];
}

void init()
{
    dp.assign(n + 1 ,vl(5 ,0));
    v.assign(n + 1 ,vl(4 ,INT_MAX));

    dp[n][3] = -1;
    dp[n][4] = -1;

/// --- State of main vector --- ///
/// v[i][0] = L
/// v[i][1] = R
/// v[i][2] = C
/// v[i][3] = Idx

/// --- State of dp vector --- ///
/// dp[i][0] = cnt
/// dp[i][1] = score
/// dp[i][2] = dur
/// dp[i][3] = par
/// dp[i][4] = ref
}

int lowerBound(int L ,int R ,ll val)
{
    while( L < R - 1 )
    {
        int Mid = (L + R) >> 1;

        v[Mid][0] >= val ? R = Mid : L = Mid;
    }

    return v[L][0] >= val ? L : R;
}

int main()
{
    scanf("%d" ,&n);  init();

    for(int i = 0 ; i < n ; i++)
    {
        scanf("%lld" ,&v[i][0]);
        scanf("%lld" ,&v[i][1]);
        scanf("%lld" ,&v[i][2]);
        v[i][3] = i + 1;
    }

    sort(v.begin() ,v.begin() + n ,cmp);

    for(int i = n - 1 ; i >= 0 ; i--)
    {
        int j = lowerBound(i + 1 ,n ,v[i][1]);

        dp[i][3] = j;
        dp[i][4] = -1;
        dp[i][0] = dp[j][0] + 1;
        dp[i][1] = dp[j][1] + v[i][2];
        dp[i][2] = dp[j][2] + v[i][1] - v[i][0];

        if( dp[i][1] == dp[i + 1][1] )
        {
            if( dp[i][2] > dp[i + 1][2] )
            {
                dp[i] = dp[i + 1];
                dp[i][3] = -1;
                dp[i][4] = i + 1;
            }
        }
        else if( dp[i][1] < dp[i + 1][1] )
        {
            dp[i] = dp[i + 1];
            dp[i][3] = -1;
            dp[i][4] = i + 1;
        }
    }

    int i = 0;
    printf("%lld %lld %lld\n" ,dp[i][0] ,dp[i][1] ,dp[i][2]);

    while( dp[i][3] != -1 || dp[i][4] != -1 )
    {
        if( dp[i][3] != -1 )
        {
            printf("%lld " ,v[i][3]);
            i = dp[i][3];
        }
        else i = dp[i][4];
    }

    return 0;
}