Submission #1357168


Source Code Expand

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;

public class Program
{
    static readonly int Mod = (int)1e9 + 7;
    static void Add(ref int a, int b) { if ((a += b) >= Mod) a -= Mod; }

    public void Solve()
    {
        int N = Reader.Int(), K = Reader.Int();
        var dp = new int[N * 2 + 2];

        dp[1] = 1;
        for (int A = 1; A <= N; A++)
            dp[A << 1] = 1;
        for (int i = 0, val; i < K; i++)
        {
            var nextdp = new int[dp.Length];
            for (int A = 0; A <= N; A++)
                for (int seenZero = 0; seenZero < 2; seenZero++)
                    if ((val = dp[A << 1 | seenZero]) > 0)
                        for (int a1 = 0; a1 < 2; a1++)
                            for (int a2 = 0; a2 < 2; a2++)
                                if (A - a1 >= 0 && A - a1 < N)
                                {
                                    int nextSeenZero = seenZero | (A - a1 == 0 ? 1 : 0);
                                    Add(ref nextdp[A - a1 + 1 - a2 << 1 | nextSeenZero], val);
                                }
            dp = nextdp;
        }

        long ans = Enu.Range(0, N + 1).Sum(i => (long)dp[i << 1 | 1]) % Mod;
        Console.WriteLine(ans);
    }
}


class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { Dispose(); A = new string[0]; }
    public static void Set(TextReader r) { Init(); reader = r; }
    public static void Set(string file) { Init(); reader = new StreamReader(file); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    public static void Dispose() { reader.Dispose(); }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

Submission Info

Submission Time
Task D - Piling Up
User eitaho
Language C# (Mono 4.6.2.0)
Score 900
Code Size 3270 Byte
Status AC
Exec Time 518 ms
Memory 28376 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt
Case Name Status Exec Time Memory
sample_01.txt AC 24 ms 9300 KB
sample_02.txt AC 25 ms 11252 KB
sample_03.txt AC 232 ms 27616 KB
subtask_1_01.txt AC 76 ms 22624 KB
subtask_1_02.txt AC 56 ms 11348 KB
subtask_1_03.txt AC 180 ms 13380 KB
subtask_1_04.txt AC 160 ms 28128 KB
subtask_1_05.txt AC 377 ms 27864 KB
subtask_1_06.txt AC 181 ms 13380 KB
subtask_1_07.txt AC 203 ms 13376 KB
subtask_1_08.txt AC 81 ms 15312 KB
subtask_1_09.txt AC 387 ms 28376 KB
subtask_1_10.txt AC 518 ms 27856 KB
subtask_1_11.txt AC 180 ms 13380 KB
subtask_1_12.txt AC 122 ms 13384 KB
subtask_1_13.txt AC 163 ms 15432 KB
subtask_1_14.txt AC 86 ms 15312 KB
subtask_1_15.txt AC 67 ms 15312 KB
subtask_1_16.txt AC 211 ms 13376 KB
subtask_1_17.txt AC 80 ms 15440 KB
subtask_1_18.txt AC 93 ms 13388 KB
subtask_1_19.txt AC 100 ms 13388 KB
subtask_1_20.txt AC 231 ms 25568 KB
subtask_1_21.txt AC 24 ms 9172 KB
subtask_1_22.txt AC 24 ms 11220 KB
subtask_1_23.txt AC 23 ms 9300 KB
subtask_1_24.txt AC 24 ms 11348 KB
subtask_1_25.txt AC 23 ms 9172 KB
subtask_1_26.txt AC 24 ms 9300 KB
subtask_1_27.txt AC 24 ms 9172 KB