140492025-01-09 17:58:24MorvaiVarkonyBenzinkút üzemeltetés (55)cpp17Time limit exceeded 0/55287ms512 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=1;
    int b=i+1;
    while (a!=b) {
        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 << " ";
  }
}
SubtaskSumTestVerdictTimeMemory
base0/55
1Time limit exceeded0/0287ms316 KiB
2Time limit exceeded0/0287ms316 KiB
3Time limit exceeded0/3284ms508 KiB
4Time limit exceeded0/3286ms316 KiB
5Time limit exceeded0/3273ms508 KiB
6Time limit exceeded0/3273ms316 KiB
7Time limit exceeded0/3275ms512 KiB
8Time limit exceeded0/3275ms316 KiB
9Time limit exceeded0/3282ms316 KiB
10Time limit exceeded0/3282ms500 KiB
11Time limit exceeded0/3284ms316 KiB
12Time limit exceeded0/3284ms316 KiB
13Time limit exceeded0/4284ms508 KiB
14Time limit exceeded0/4284ms316 KiB
15Time limit exceeded0/5287ms316 KiB
16Time limit exceeded0/6287ms316 KiB
17Time limit exceeded0/6282ms316 KiB