204272026-01-06 18:14:21ZsoltBenzinkút üzemeltetés (55)cpp17Elfogadva 55/551ms508 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>tav(n+1);
    vector<int>penz(n+1);
    for(int i=1; i<=n; i++)
    {
        cin>>tav[i]>>penz[i];
    }
    vector<int>profit(n+1,0);
    vector<int>epit(n+1,0);
    profit[1]=penz[1];
    epit[1]=penz[1]>0;
    int j,bal,jobb,kozep;
    for(int i=1; i<=n; i++)
    {
        j=0, bal=1, jobb=i-1;

        while(bal<=jobb)
        {
            kozep=(bal+jobb)/2;
            if(tav[i]-tav[kozep]>=k)
            {
                j=kozep;
                bal=kozep+1;
            }
            else
            {
                jobb=kozep-1;
            }
        }

        if(penz[i]+profit[j]>profit[i-1])
        {
            profit[i]=penz[i]+profit[j];
            epit[i]=j;
        }
        else
        {
            profit[i]=profit[i-1];
            epit[i]=-1;
        }
    }
    vector<int>a;
    int i=n;
    while(i>=1)
    {
        if(epit[i]!=-1)
        {
            a.push_back(i);
            i=epit[i];
        }
        else
        {
            i--;
        }
    }
    cout<<profit[n]<<endl;
    cout<<a.size()<<" ";
    reverse(a.begin(),a.end());
    for(auto x:a)
    {
        cout<<x<<" ";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base55/55
1Elfogadva0/01ms508 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva3/31ms316 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms332 KiB
6Elfogadva3/31ms316 KiB
7Elfogadva3/31ms508 KiB
8Elfogadva3/31ms316 KiB
9Elfogadva3/31ms316 KiB
10Elfogadva3/31ms316 KiB
11Elfogadva3/31ms316 KiB
12Elfogadva3/31ms316 KiB
13Elfogadva4/41ms316 KiB
14Elfogadva4/41ms400 KiB
15Elfogadva5/51ms316 KiB
16Elfogadva6/61ms316 KiB
17Elfogadva6/61ms316 KiB