228912026-01-16 07:38:25badamBenzinkút üzemeltetés (55)cpp17Elfogadva 55/553ms548 KiB
#include <bits/stdc++.h>

using namespace std;
struct hely
{
    int tav, haszon;
};
int main()
{   ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, szamlalo=0;
    cin>>n>>k;
    hely t[n+1];
    t[0].haszon=0;
    t[0].tav=-2e9;
    int veg=0;
    for(int i=1; i<=n; i++) cin>>t[i].tav>>t[i].haszon;
    int maxi[n+1], jelenlegi_max=0;
    maxi[0]=0;
    for(int i=1; i<=n; i++) maxi[i]=0;
    vector <bool> v(n+1,false);
    vector <int> v1(n+1,0);
    for(int i=1; i<=n; i++)
    {
        int j=0;
        while(t[i].tav-t[j].tav>=k)
        {
            int most_haszon=t[i].haszon+maxi[j];
            if(most_haszon>maxi[i]) maxi[i]=most_haszon, v1[i]=j;
            j++;
        }
        if(maxi[i]>jelenlegi_max)
        {
            jelenlegi_max=maxi[i];
            veg=i;
        }
    }
    cout << jelenlegi_max << endl;
    vector <int> utvonal;
    while(veg!=0)
    {
        utvonal.push_back(veg);
        veg=v1[veg];
    }
    cout << utvonal.size() << " ";
    sort(utvonal.begin(),utvonal.end());
    for(int x:utvonal)cout<<x<<" ";


    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base55/55
1Elfogadva0/02ms508 KiB
2Elfogadva0/03ms316 KiB
3Elfogadva3/32ms316 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/32ms316 KiB
6Elfogadva3/31ms316 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva3/31ms316 KiB
9Elfogadva3/32ms508 KiB
10Elfogadva3/32ms316 KiB
11Elfogadva3/32ms316 KiB
12Elfogadva3/32ms316 KiB
13Elfogadva4/41ms500 KiB
14Elfogadva4/41ms356 KiB
15Elfogadva5/51ms316 KiB
16Elfogadva6/62ms548 KiB
17Elfogadva6/62ms500 KiB