AtCoder Grand Contest 013

Submission #1357175

Source codeソースコード

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++)
                            if (A - a1 >= 0 && A - a1 < N)
                                for (int a2 = 0; a2 < 2; a2++)
                                {
                                    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

Task問題 D - Piling Up
User nameユーザ名 eitaho
Created time投稿日時
Language言語 C# (Mono 4.6.2.0)
Status状態 AC
Score得点 900
Source lengthソースコード長 3270 Byte
File nameファイル名
Exec time実行時間 515 ms
Memory usageメモリ使用量 28128 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
All 900 / 900 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 24 ms 11220 KB
sample_02.txt AC 24 ms 11124 KB
sample_03.txt AC 232 ms 25568 KB
subtask_1_01.txt AC 76 ms 20576 KB
subtask_1_02.txt AC 56 ms 11348 KB
subtask_1_03.txt AC 181 ms 15428 KB
subtask_1_04.txt AC 160 ms 28128 KB
subtask_1_05.txt AC 377 ms 25816 KB
subtask_1_06.txt AC 181 ms 13380 KB
subtask_1_07.txt AC 202 ms 13376 KB
subtask_1_08.txt AC 80 ms 15440 KB
subtask_1_09.txt AC 387 ms 26328 KB
subtask_1_10.txt AC 515 ms 27856 KB
subtask_1_11.txt AC 179 ms 15428 KB
subtask_1_12.txt AC 122 ms 15432 KB
subtask_1_13.txt AC 162 ms 13384 KB
subtask_1_14.txt AC 85 ms 13392 KB
subtask_1_15.txt AC 66 ms 15440 KB
subtask_1_16.txt AC 211 ms 15424 KB
subtask_1_17.txt AC 79 ms 13392 KB
subtask_1_18.txt AC 93 ms 15436 KB
subtask_1_19.txt AC 100 ms 15436 KB
subtask_1_20.txt AC 232 ms 25568 KB
subtask_1_21.txt AC 24 ms 11348 KB
subtask_1_22.txt AC 23 ms 9300 KB
subtask_1_23.txt AC 24 ms 11220 KB
subtask_1_24.txt AC 24 ms 11220 KB
subtask_1_25.txt AC 23 ms 9172 KB
subtask_1_26.txt AC 24 ms 9300 KB
subtask_1_27.txt AC 23 ms 9300 KB