81902024-01-12 17:28:56ananászBenzinkút üzemeltetés (55)csharpAccepted 55/5535ms23944 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();
        }
    }
}
SubtaskSumTestVerdictTimeMemory
base55/55
1Accepted0/032ms21116 KiB
2Accepted0/034ms21732 KiB
3Accepted3/332ms21896 KiB
4Accepted3/330ms21988 KiB
5Accepted3/330ms22120 KiB
6Accepted3/329ms22492 KiB
7Accepted3/330ms22920 KiB
8Accepted3/332ms22708 KiB
9Accepted3/332ms23276 KiB
10Accepted3/332ms23108 KiB
11Accepted3/330ms23888 KiB
12Accepted3/332ms23792 KiB
13Accepted4/432ms23912 KiB
14Accepted4/432ms23772 KiB
15Accepted5/532ms23680 KiB
16Accepted6/634ms23696 KiB
17Accepted6/635ms23944 KiB