244022026-02-11 08:42:04KisKocsogBenzinkút üzemeltetés (55)cpp17Hibás válasz 0/552ms544 KiB
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct piheno{
    long long tav,hat;
};

struct valami{
    long long tav,hat,p;
};

int main()
{
    //ifstream f("genyo.txt");

    long long n,k;
    cin>>n>>k;

    piheno a[n];
    valami opt[n];
    piheno legjobb;

    for(int i=0;i<n;i++){
        cin>>a[i].tav>>a[i].hat;
        //f>>a[i].tav>>a[i].hat;
    }

    legjobb.tav = n-1;
    legjobb.hat = a[n-1].hat;

    piheno kovi;
    kovi.hat=0;

    for(int i=n-1;i>=0;i--){
        opt[i].hat = a[i].hat;
        opt[i].tav = a[i].tav;
        kovi.hat=0;
        for(int j=i+1;j<n;j++){
            if(a[j].tav - opt[i].tav >= k){
                if(opt[j].hat>kovi.hat)
                {
                    kovi.hat = opt[j].hat;
                    kovi.tav = j;
                }
            }

        }
        if(kovi.hat!=0){
            opt[i].hat = a[i].hat + opt[kovi.tav].hat;
            opt[i].p = kovi.tav;
        }else{
            opt[i].p = n;
        }

    }

    piheno startPoint;
    startPoint.hat = 0;

    for(int i=0;i<n;i++){
        if(opt[i].hat > startPoint.hat){
            startPoint.hat = opt[i].hat;
            startPoint.tav = i;
        }
    }
    int d=0;
    queue <long long> benzinkutak;
    while(startPoint.tav!=n){
        benzinkutak.push(startPoint.tav+1);
        d++;
        startPoint.tav = opt[startPoint.tav].p;

    }
    cout<<d<<" ";
    while(!benzinkutak.empty()){
        cout<<benzinkutak.front()<<" ";
        benzinkutak.pop();
    }




    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/55
1Hibás válasz0/01ms544 KiB
2Hibás válasz0/02ms316 KiB
3Hibás válasz0/31ms508 KiB
4Hibás válasz0/31ms316 KiB
5Hibás válasz0/31ms316 KiB
6Hibás válasz0/31ms316 KiB
7Hibás válasz0/31ms316 KiB
8Hibás válasz0/31ms316 KiB
9Hibás válasz0/31ms316 KiB
10Hibás válasz0/31ms316 KiB
11Hibás válasz0/31ms316 KiB
12Hibás válasz0/31ms408 KiB
13Hibás válasz0/41ms316 KiB
14Hibás válasz0/42ms412 KiB
15Hibás válasz0/52ms316 KiB
16Hibás válasz0/62ms316 KiB
17Hibás válasz0/62ms316 KiB