Submission #37157390

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;

namespace Tasks
{
    public class D
    {
        public static void Main()
        {
            using var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var (N, K, D) = Scanner.Scan<int, int, int>();
            var A = Scanner.ScanEnumerable<long>().ToArray();
            var dp = new bool[N + 1, K + 1, D];
            dp[0, 0, 0] = true;
            var dpMax = new long[N + 1, K + 1, D];
            const long inf = (long)1e18;
            for (var i = 0; i <= N; i++)
            {
                for (var k = 0; k <= K; k++)
                {
                    for (var d = 0; d < D; d++)
                    {
                        dpMax[i, k, d] = -inf;
                    }
                }
            }

            dpMax[0, 0, 0] = 0;

            for (var i = 0; i < N; i++)
            {
                for (var k = 0; k <= K; k++)
                {
                    for (var u = 0; u < D; u++)
                    {
                        var v = (u + A[i]) % D;
                        dp[i + 1, k, u] |= dp[i, k, u];
                        dpMax[i + 1, k, u] = Math.Max(dpMax[i + 1, k, u], dpMax[i, k, u]);
                        if (k + 1 <= K)
                        {
                            dp[i + 1, k + 1, v] |= dp[i, k, u];
                            dpMax[i + 1, k + 1, v] = Math.Max(dpMax[i + 1, k + 1, v], dpMax[i, k, u] + A[i]);
                        }
                    }
                }
            }

            var answer = dp[N, K, 0] ? dpMax[N, K, 0] : -1;
            Console.WriteLine(answer);
        }

        public static class Scanner
        {
            public static T Scan<T>() where T : IConvertible => Convert<T>(Scan()[0]);
            public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
            {
                var buffer = Scan();
                return (Convert<T1>(buffer[0]), Convert<T2>(buffer[1]));
            }
            public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
            {
                var buffer = Scan();
                return (Convert<T1>(buffer[0]), Convert<T2>(buffer[1]), Convert<T3>(buffer[2]));
            }
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
            {
                var buffer = Scan();
                return (Convert<T1>(buffer[0]), Convert<T2>(buffer[1]), Convert<T3>(buffer[2]), Convert<T4>(buffer[3]));
            }
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
            {
                var buffer = Scan();
                return (Convert<T1>(buffer[0]), Convert<T2>(buffer[1]), Convert<T3>(buffer[2]), Convert<T4>(buffer[3]), Convert<T5>(buffer[4]));
            }
            public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
            {
                var buffer = Scan();
                return (Convert<T1>(buffer[0]), Convert<T2>(buffer[1]), Convert<T3>(buffer[2]), Convert<T4>(buffer[3]), Convert<T5>(buffer[4]), Convert<T6>(buffer[5]));
            }
            public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => Scan().Select(Convert<T>);
            private static string[] Scan()
            {
                var line = Console.ReadLine()?.Trim() ?? string.Empty;
                return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
            }
            private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
        }
    }
}

Submission Info

Judge Result