5749 2023-09-16 11:43:56 Ablablabla Benzinkút üzemeltetés (55) cpp17 Hibás válasz 6/55 32ms 35240 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";
}