212472026-01-12 17:27:02algoproBenzinkút üzemeltetés (55)cpp17Elfogadva 55/553ms1588 KiB
// UUID: 43cd5f20-55f7-4b27-a024-7b4f3ed34229
//AB
//Feladat linkje: 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, mintav;
    cin >> n >> mintav;
    vector<int> tav(n+1);
    vector<int> haszon(n+1);
    vector<int> dp(n+1, 0);
    vector<vector<int>> eredmeny(n+1);
    for (int i = 1; i <= n; i++) {//beolv
        cin >> tav[i] >> haszon[i];
    }
    for (int i = 1; i <= n; i++) {//dpszamol
        int j = i;
        while(j > 0 && tav[i]-tav[j] < mintav) {
			j--;
		}//dp[i] = max(dp[i-1], dp[j]+haszon[i]);
        if (dp[i-1] > dp[j]+haszon[i]) {
            dp[i] = dp[i-1];
            eredmeny[i] = eredmeny[i-1];
        } else {
            dp[i] = dp[j]+haszon[i];
            eredmeny[i] = eredmeny[j];
            eredmeny[i].push_back(i);
        }
		
    }
	cout << dp[n] <<"\n";
	cout << eredmeny[n].size() <<" ";
    for(int i : eredmeny[n]) {
        cout << i << " ";
    }
    
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base55/55
1Elfogadva0/01ms316 KiB
2Elfogadva0/03ms1588 KiB
3Elfogadva3/31ms316 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms316 KiB
6Elfogadva3/31ms316 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva3/31ms316 KiB
9Elfogadva3/31ms316 KiB
10Elfogadva3/31ms316 KiB
11Elfogadva3/31ms316 KiB
12Elfogadva3/31ms564 KiB
13Elfogadva4/42ms820 KiB
14Elfogadva4/42ms1172 KiB
15Elfogadva5/52ms1152 KiB
16Elfogadva6/62ms1332 KiB
17Elfogadva6/62ms1568 KiB