Submission #5411369


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var N = line[0];
            var K = line[1];

            var dp = new int[N, 2];
            dp[0, 1] = 1;
            for (int i = 1; i < K - 1; i++)
            {
                dp[i, 0] = dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 1]) % mod;
            }
            {
                int i = K - 1;

                dp[i, 0] = (dp[i - 1, 0] + dp[i - 1, 1]) % mod;
                dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 1] - 1) % mod;
            }
            for (int i = K; i < N; i++)
            {
                dp[i, 0] = (dp[i - 1, 0] + dp[i - 1, 1]) % mod;
                dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 1] - dp[i - K, 0]) % mod;
                if (dp[i, 1] < 0)
                    dp[i, 1] += mod;
            }
            return dp[N - 1, 1];
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
        public static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Submission Info

Submission Time
Task F - 準急
User kzrnm
Language C# (Mono 4.6.2.0)
Score 4
Code Size 2815 Byte
Status AC
Exec Time 50 ms
Memory 18912 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 49 ms 18912 KB
01 AC 37 ms 16864 KB
02 AC 35 ms 12512 KB
03 AC 34 ms 15584 KB
04 AC 50 ms 18272 KB
90 AC 24 ms 13268 KB
91 AC 23 ms 9172 KB