140612025-01-09 18:02:11MorvaiVarkonyBenzinkút üzemeltetés (55)cpp17Elfogadva 55/553ms1588 KiB
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main()
{
  int n,k;
  cin >> n >> k;
  vector<pair<int,int>> v(n+1);
  vector<int> maxi(n+1);
  vector<vector<int>> helyek(n+1);
  v[0].first=-1000000;
  v[0].second=0;
  for (int i=1; i<=n; i++) {
    cin >> v[i].first;
    cin >> v[i].second;
    int a=0;
    int b=i+1;
    while (b-a>1) {
        int c=(a+b)/2;
        if (v[i].first-v[c].first>=k) {
            a=c;
        }
        else {
            b=c;
        }
    }
    int dp=maxi[a]+v[i].second;
    if (maxi[i-1]<dp) {
        maxi[i]=dp;
        helyek[i]=helyek[a];
        helyek[i].push_back(i);
    }
    else {
        maxi[i]=maxi[i-1];
        helyek[i]=helyek[i-1];
    }
  }
  cout << maxi[n] << "\n";
  cout << helyek[n].size() << " ";
  for (int i:helyek[n]) {
    cout << i << " ";
  }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base55/55
1Elfogadva0/01ms316 KiB
2Elfogadva0/03ms1588 KiB
3Elfogadva3/31ms508 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms328 KiB
6Elfogadva3/31ms316 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva3/31ms508 KiB
9Elfogadva3/31ms316 KiB
10Elfogadva3/31ms316 KiB
11Elfogadva3/31ms316 KiB
12Elfogadva3/32ms568 KiB
13Elfogadva4/42ms820 KiB
14Elfogadva4/42ms820 KiB
15Elfogadva5/52ms1076 KiB
16Elfogadva6/62ms1332 KiB
17Elfogadva6/63ms1444 KiB