133942025-01-07 19:10:21sarminBenzinkút üzemeltetés (55)cpp17Elfogadva 55/553ms1780 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {

    int n, k; cin >> n >> k;
    vector<pair<int, int>> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    vector<int> dp(n + 1, 0);
    vector<vector<int>> honnan(n + 1);
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x > 0 && v[i].first - v[x].first < k) x--;
        dp[i] = max(dp[x] + v[i].second, dp[i - 1]);
        if (dp[i] != dp[i - 1]) {
            honnan[i] = honnan[x];
            honnan[i].push_back(i);
        } else {
            honnan[i] = honnan[i - 1];
        }
    }

    cout << dp[n] << endl << honnan[n].size() << " ";
    for (int& x : honnan[n]) cout << x << " ";

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base55/55
1Elfogadva0/01ms508 KiB
2Elfogadva0/03ms1780 KiB
3Elfogadva3/31ms316 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms316 KiB
6Elfogadva3/31ms508 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva3/31ms328 KiB
9Elfogadva3/31ms320 KiB
10Elfogadva3/31ms316 KiB
11Elfogadva3/31ms316 KiB
12Elfogadva3/32ms644 KiB
13Elfogadva4/42ms824 KiB
14Elfogadva4/42ms896 KiB
15Elfogadva5/52ms1080 KiB
16Elfogadva6/62ms1332 KiB
17Elfogadva6/62ms1336 KiB