140372025-01-09 17:47:36MorvaiVarkonyBenzinkút üzemeltetés (55)cpp17Wrong answer 12/552ms528 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=0;
  v[0].second=-1000000;
  for (int i=1; i<=n; i++) {
    cin >> v[i].first;
    cin >> v[i].second;
    int a=1;
    int b=n;
    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 << " ";
  }
}
SubtaskSumTestVerdictTimeMemory
base12/55
1Accepted0/01ms316 KiB
2Wrong answer0/02ms528 KiB
3Wrong answer0/31ms512 KiB
4Accepted3/31ms316 KiB
5Accepted3/31ms320 KiB
6Accepted3/31ms316 KiB
7Accepted3/31ms316 KiB
8Wrong answer0/31ms316 KiB
9Wrong answer0/31ms316 KiB
10Wrong answer0/31ms316 KiB
11Wrong answer0/31ms412 KiB
12Wrong answer0/31ms316 KiB
13Wrong answer0/42ms316 KiB
14Wrong answer0/42ms316 KiB
15Wrong answer0/52ms316 KiB
16Wrong answer0/62ms316 KiB
17Wrong answer0/62ms324 KiB