229672026-01-16 09:59:20KassayAkosBenzinkút üzemeltetés (55)cpp17Hibás válasz 18/552ms604 KiB
#include <bits/stdc++.h>

using namespace std;



int main()
{
    int n, k;
    cin>>n>>k;
    vector <int> tav(n);
    vector <int> hasz(n);
    for (int i=0;i<n;i++)
    {
        cin>>tav[i]>>hasz[i];
    }
    vector <int> maxh(n,0);
    vector <int> epit(n, 0);
    vector <int> honnan(n, 0);
    maxh[0]=hasz[0];
    epit[0]=1;
    int j, akthasz;
    for (int i=1;i<n;i++)
    {
        j=i-1;
        while (j>=0 && tav[i]-tav[j]<k)
        {
            j--;
        }
        akthasz=hasz[i];
        if (j>=0)
        {
            akthasz+=maxh[j];
        }
        if (akthasz>maxh[i-1])
        {
            maxh[i]=akthasz;
            epit[i]=1;
            honnan[i]=j;
        }
        else
        {
            maxh[i]=maxh[i-1];
        }
    }
    int maxi=INT_MIN;
    for (int i=n-1;i>=0;i--)
    {
        maxi=max(maxi,maxh[i]);
    }
    /*
5 20
10 10
20 40
30 10
40 20
50 30
    */
    cout<<maxi<<endl;
    vector <int> megoldas;
    int i=n-1;
    while (i>0)
    {
        if (epit[i]==1 && maxh[i]==hasz[i]+(honnan[i]>0 ? maxh[honnan[i]] : 0))
        {
            megoldas.push_back(i+1);
            i=honnan[i];
        }
        else
        {
            i--;
        }
    }
    reverse (megoldas.begin(), megoldas.end());
    int len=megoldas.size();
    cout<<len<< " ";
    for (int i=0;i<len;i++)
    {
        cout<<megoldas[i]<<" ";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base18/55
1Elfogadva0/01ms316 KiB
2Hibás válasz0/02ms316 KiB
3Hibás válasz0/31ms316 KiB
4Hibás válasz0/31ms500 KiB
5Elfogadva3/31ms508 KiB
6Hibás válasz0/31ms500 KiB
7Elfogadva3/31ms316 KiB
8Hibás válasz0/31ms316 KiB
9Hibás válasz0/31ms316 KiB
10Hibás válasz0/31ms336 KiB
11Hibás válasz0/31ms316 KiB
12Hibás válasz0/32ms604 KiB
13Hibás válasz0/41ms316 KiB
14Hibás válasz0/41ms316 KiB
15Hibás válasz0/51ms316 KiB
16Elfogadva6/61ms388 KiB
17Elfogadva6/61ms316 KiB