7995 2024. 01. 12 09:51:21 TortelliniJr Benzinkút üzemeltetés (55) csharp Elfogadva 55/55 50ms 28952 KiB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace benzinkut
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] inp = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int n = inp[0];
            int min = inp[1];
            int[] helyk = new int[n];
            int[] stonks = new int[n];
            int[] ovr = new int[n];
            for (int f = 0; f < n; f++)
            {
                inp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                helyk[f] = inp[0];
                stonks[f] = inp[1];
            }
            int max = helyk[n - 1];
            int i = n - 1;
            int[] ovrn = new int[n];
            while (helyk[i] > max - min)
            {
                ovr[i] = stonks[i];
                ovrn[i] = 1;
                i--;
            }
            int locmax = 0;
            int locmaxn = 0;
            for (int f = i; f >= 0; f--)
            {
                for (int k = 1; k < n - f; k++)
                {
                    if (helyk[f + k] >= helyk[f] + min && ovr[f + k] > locmax)
                    {
                        locmax = ovr[f + k];
                        locmaxn = ovrn[f + k];
                    }
                }
                ovr[f] = locmax + stonks[f];
                ovrn[f] = locmaxn + 1;
                locmax = 0;
            }
            List<int> sol = new List<int>();
            sol.Add(ovr.ToList().IndexOf(ovr.Max()));
            for (int f = ovr.ToList().IndexOf(ovr.Max()); f < n;)
            {
                locmax = 0;
                for (int k = 1; k < n - f; k++)
                {
                    if (helyk[f + k] >= helyk[f] + min && ovr[f + k] > locmax)
                    {
                        locmax = ovr[f + k];
                        locmaxn = f + k;
                    }
                }
                if (f != locmaxn)
                {
                    f = locmaxn;
                    sol.Add(locmaxn);
                }
                else
                {
                    break;
                }
            }
            Console.WriteLine(ovr.Max());
            Console.Write(ovrn[ovr.ToList().IndexOf(ovr.Max())] + " ");
            for (int k = 0; k < ovrn[ovr.ToList().IndexOf(ovr.Max())]; k++)
            {
                Console.Write((sol[k] + 1) + " ");
            }
            Console.ReadLine();
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 55/55
1 Elfogadva 0/0 35ms 22532 KiB
2 Elfogadva 0/0 50ms 25736 KiB
3 Elfogadva 3/3 35ms 23016 KiB
4 Elfogadva 3/3 34ms 23556 KiB
5 Elfogadva 3/3 35ms 23708 KiB
6 Elfogadva 3/3 34ms 23680 KiB
7 Elfogadva 3/3 35ms 24116 KiB
8 Elfogadva 3/3 35ms 24148 KiB
9 Elfogadva 3/3 37ms 24388 KiB
10 Elfogadva 3/3 35ms 24472 KiB
11 Elfogadva 3/3 35ms 24980 KiB
12 Elfogadva 3/3 39ms 26008 KiB
13 Elfogadva 4/4 41ms 26752 KiB
14 Elfogadva 4/4 43ms 26988 KiB
15 Elfogadva 5/5 43ms 27440 KiB
16 Elfogadva 6/6 45ms 28304 KiB
17 Elfogadva 6/6 48ms 28952 KiB