8190 2024. 01. 12 17:28:56 ananász Benzinkút üzemeltetés (55) csharp Elfogadva 55/55 35ms 23944 KiB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace benzinkut
{
    class Program
    {
        struct kut
        {
            public int sum;
            public int tav;
            public int elozo;
        }
        static void Main(string[] args)
        {
            string[] st = Console.ReadLine().Split();
            int N = int.Parse(st[0]);
            int K = int.Parse(st[1]);
            kut[] T = new kut[N + 1];
            T[0].sum = 0;
            T[0].tav = 0;
            T[0].elozo = 0; 
            for (int i = 1; i < N + 1; i++)
            {
                st = Console.ReadLine().Split();
                T[i].tav = int.Parse(st[0]);
                T[i].sum = int.Parse(st[1]);
                int cv = i;
                while (cv >= 1 && T[i].tav - T[cv].tav < K) //vissza addig amikor már van vele kompatibilis benzinkút
                {
                    cv--;
                }
                int maxid = cv;
                while (cv>=1)
                { 
                    cv--;
                    if (T[maxid].sum<T[cv].sum)
                    {
                        maxid = cv;
                    }
                }
                T[i].sum += T[maxid].sum;
                T[i].elozo = maxid;
            }
            int id = N;
            int max = 0;
            while (id>=1)
            {
                if (T[id].sum>T[max].sum)
                {
                    max = id;
                }
                id--;
            }
            Console.WriteLine(T[max].sum);
            List<int> epit = new List<int>();
            epit.Add(max);
            while (T[max].elozo!=0)
            {
                epit.Add(T[max].elozo);
                max = T[max].elozo;
            }
            epit.Reverse();
            Console.WriteLine($"{epit.Count} {string.Join(" ",epit)}");
            Console.ReadKey();
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 55/55
1 Elfogadva 0/0 32ms 21116 KiB
2 Elfogadva 0/0 34ms 21732 KiB
3 Elfogadva 3/3 32ms 21896 KiB
4 Elfogadva 3/3 30ms 21988 KiB
5 Elfogadva 3/3 30ms 22120 KiB
6 Elfogadva 3/3 29ms 22492 KiB
7 Elfogadva 3/3 30ms 22920 KiB
8 Elfogadva 3/3 32ms 22708 KiB
9 Elfogadva 3/3 32ms 23276 KiB
10 Elfogadva 3/3 32ms 23108 KiB
11 Elfogadva 3/3 30ms 23888 KiB
12 Elfogadva 3/3 32ms 23792 KiB
13 Elfogadva 4/4 32ms 23912 KiB
14 Elfogadva 4/4 32ms 23772 KiB
15 Elfogadva 5/5 32ms 23680 KiB
16 Elfogadva 6/6 34ms 23696 KiB
17 Elfogadva 6/6 35ms 23944 KiB