79952024-01-12 09:51:21TortelliniJrBenzinkút üzemeltetés (55)csharpAccepted 55/5550ms28952 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();
        }
    }
}
SubtaskSumTestVerdictTimeMemory
base55/55
1Accepted0/035ms22532 KiB
2Accepted0/050ms25736 KiB
3Accepted3/335ms23016 KiB
4Accepted3/334ms23556 KiB
5Accepted3/335ms23708 KiB
6Accepted3/334ms23680 KiB
7Accepted3/335ms24116 KiB
8Accepted3/335ms24148 KiB
9Accepted3/337ms24388 KiB
10Accepted3/335ms24472 KiB
11Accepted3/335ms24980 KiB
12Accepted3/339ms26008 KiB
13Accepted4/441ms26752 KiB
14Accepted4/443ms26988 KiB
15Accepted5/543ms27440 KiB
16Accepted6/645ms28304 KiB
17Accepted6/648ms28952 KiB