212472026-01-12 17:27:02algoproBenzinkút üzemeltetés (55)cpp17Accepted 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 << " ";
    }
    
}
SubtaskSumTestVerdictTimeMemory
base55/55
1Accepted0/01ms316 KiB
2Accepted0/03ms1588 KiB
3Accepted3/31ms316 KiB
4Accepted3/31ms316 KiB
5Accepted3/31ms316 KiB
6Accepted3/31ms316 KiB
7Accepted3/31ms316 KiB
8Accepted3/31ms316 KiB
9Accepted3/31ms316 KiB
10Accepted3/31ms316 KiB
11Accepted3/31ms316 KiB
12Accepted3/31ms564 KiB
13Accepted4/42ms820 KiB
14Accepted4/42ms1172 KiB
15Accepted5/52ms1152 KiB
16Accepted6/62ms1332 KiB
17Accepted6/62ms1568 KiB