57492023-09-16 11:43:56AblablablaBenzinkút üzemeltetés (55)cpp17Hibás válasz 6/5532ms35240 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

ll n, k;
vector<ll> tavok;
vector<ll> haszon;
vector<vector<pii>> dp;

ll megold(ll akt, ll elozo){
    if(akt == n + 1){
        return 0;
    } else if(dp[akt][elozo] != (pii){-1, -1}){
        return dp[akt][elozo].first;
    }

    ll a = 0;
    ll b = megold(akt + 1, elozo);

    if(tavok[akt] - tavok[elozo] >= k){
        a = megold(akt + 1, akt) + haszon[akt];
    }

    if(a > b){
        dp[akt][elozo] = {a, 0};
    } else{
        dp[akt][elozo] = {b, 1};
    }

    return dp[akt][elozo].first;
}



int main()
{
    cin >> n >> k;

    tavok.assign(n + 1, 0);
    haszon.assign(n + 1, 0);
    tavok[0] = 0 - k - 1;
    haszon[0] = 0 - k - 1;

    for(ll i = 1; i <= n; i++){
        cin >> tavok[i] >> haszon[i];
    }

    dp.assign(n + 1, vector<pii>(n + 1, {-1, -1}));
    ll maxi = megold(1, 0);
    cout << maxi << "\n";

    ll akt = 1;
    ll elozo = 0;
    vector<ll> kutak;

    while(akt <= n){
        if(dp[akt][elozo].second == 0){
            kutak.push_back(akt);
            akt++;
            elozo = akt;
        } else{
            akt++;
        }
    }

    cout << kutak.size() << " ";
    for(ll x : kutak){
        cout << x << " ";
    }
    cout << "\n";
}