18962022-12-07 21:49:40sztomiMúzeumi őrökcpp17Time limit exceeded 32/40699ms17272 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e16;

int n, e, u;
vector<int> ar;
vector<int> kezd;
vector<int> veg;
vector<int> ind;
vector<pair<ll, vector<int>>> dp;
vector<bool> volt;

struct comp{
    bool operator()(int a, int b){
        if(kezd[a] < kezd[b]) return true;
        if(kezd[a] > kezd[b]) return false;
        return veg[a] < veg[b];
    }
};


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

    cin >> n >> e >> u;
    u -= e-1;
    ar.assign(n+1, 0);
    kezd.assign(n+1, 0);
    veg.assign(n+1, 0);
    ind.assign(n+1, 0);
    dp.resize(n+1);
    volt.assign(n+1, false);

    for(int i = 1; i <= n; i++){
        ind[i] = i;
        cin >> kezd[i] >> veg[i] >> ar[i];
        kezd[i] -= e-1;
        veg[i] -= e-1;
    }
    sort(ind.begin(), ind.end(), comp());

    pair<ll, vector<int>> ret, ideigl;
    for(int utolso = n; utolso >= 0; utolso--){
        if(veg[ind[utolso]] == u){
            ret = {0, vector<int>()};
        }
        else{
            ret = {inf, vector<int>()};
            for(int i = utolso+1; i <= n; i++){
                if(kezd[ind[i]] <= veg[ind[utolso]]+1){
                    ideigl = dp[i];
                    if(ideigl.first + ar[ind[i]] < ret.first){
                        ret.first = ideigl.first + ar[ind[i]];
                        ret.second = ideigl.second;
                        ret.second.push_back(ind[i]);
                    }
                }
                else{
                    break;
                }
            }
        }

        //cout << utolso << " " << ret.first << "\n";
        dp[utolso] = ret;
    }
    ret = dp[0];


    if(ret.first == inf){
        cout << "-1\n";
    }
    else{
        cout << ret.first << "\n";
        cout << ret.second.size() << " ";
        for(int i = ret.second.size()-1; i >= 0; i--){
            cout << ret.second[i] << " ";
        }
        cout << "\n";
    }
}
SubtaskSumTestVerdictTimeMemory
base32/40
1Accepted0/03ms1828 KiB
2Accepted0/024ms17272 KiB
3Accepted1/12ms2220 KiB
4Accepted3/32ms2432 KiB
5Accepted2/22ms2632 KiB
6Accepted2/22ms2836 KiB
7Accepted2/22ms3044 KiB
8Accepted2/22ms3128 KiB
9Accepted2/22ms3340 KiB
10Time limit exceeded0/2699ms7340 KiB
11Time limit exceeded0/2634ms7600 KiB
12Accepted2/22ms3648 KiB
13Accepted2/28ms4936 KiB
14Accepted3/317ms13572 KiB
15Accepted3/318ms15056 KiB
16Time limit exceeded0/2666ms7952 KiB
17Time limit exceeded0/2674ms7660 KiB
18Accepted2/22ms4044 KiB
19Accepted2/22ms4076 KiB
20Accepted2/22ms3972 KiB
21Accepted2/22ms4076 KiB