212402026-01-12 17:24:32algoproBenzinkút üzemeltetés (55)cpp17Hibás válasz 12/553ms1844 KiB
// UUID: bdaa8fff-eeea-4be8-9db9-5cf9c7c782ea
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, k; cin >> n >> k;
	vector<int> t(n);
	vector<int> h(n);
	vector<int> dp(n);
	vector<vector<int>> x(n);
	for(int i = 0; i < n; i++){
		cin >> t[i] >> h[i];
	}

	dp[0] = h[0];
	x[0].push_back(0);

	if(t[1] - t[0] > k){
		dp[1] = dp[0] + h[1];
		x[1] = x[0];
		x[1].push_back(1);
	}
	else{
		if(dp[0] > h[1]){
			dp[1] = dp[0];
			x[1] = x[0];
		}
		else{
			dp[1] = h[1];
			x[1].push_back(1);
		}
	}

	for(int i = 2; i < n; i++){
		if(t[i] - t[i-1] > k){
			dp[i] = dp[i-1] + h[i];
			x[i] = x[i-1];
			x[i].push_back(i);
		}
		else{
			dp[i] = max(dp[i-1], dp[i-2]+h[i]);
			if(dp[i-1] > dp[i-2]+h[i]){
				dp[i] = dp[i-1];
				x[i] = x[i-1];
			}
			else{
				dp[i] = dp[i-2] + h[i];
				x[i] = x[i-2];
				x[i].push_back(i);
			}
		}
	}

	cout << dp[n-1] << "\n" << x[n-1].size() << " ";
	for(int i : x[n-1]) cout << i+1 << " ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base12/55
1Elfogadva0/01ms500 KiB
2Hibás válasz0/03ms1844 KiB
3Elfogadva3/31ms316 KiB
4Hibás válasz0/31ms316 KiB
5Hibás válasz0/31ms316 KiB
6Elfogadva3/31ms316 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva3/31ms508 KiB
9Hibás válasz0/31ms316 KiB
10Hibás válasz0/31ms316 KiB
11Hibás válasz0/31ms508 KiB
12Hibás válasz0/32ms820 KiB
13Hibás válasz0/42ms1012 KiB
14Hibás válasz0/42ms1392 KiB
15Hibás válasz0/52ms1332 KiB
16Hibás válasz0/63ms1588 KiB
17Hibás válasz0/63ms1844 KiB