Submission #857548


Source Code Expand

Copy
namespace DotNetLab.Fs.Console

open System
open System.Collections.Generic

[<AutoOpen>]
module Misc =
  type Long = int64
  let inline long x = int64 x

  let readLine f = Console.ReadLine().Split([|' '|]) |> Array.map f

module Program =
  [<EntryPoint>]
  let main _ =
    let [|n; a|] = readLine int
    let xs = readLine int

    let maxX = Seq.concat [[|a|]; xs] |> Seq.max
    let maxSum = n * maxX + 1

    // dp.[j].[k].[s] = c:
    //   xs.[0..(j - 1)] から k 個を選び、その総和が s に等しいような選び方の総数が c
    let dp =
      Array.init (n + 1) (fun _ ->
        Array.init (n + 1) (fun _ ->
          Array.zeroCreate (maxSum + 1)
          ))
    dp.[0].[0].[0] <- 1L
    for j in 1..n do
      for k in 0..n do
        for s in 0..maxSum do
          dp.[j].[k].[s] <-
            if s < xs.[j - 1] then
              dp.[j - 1].[k].[s]
            elif k >= 1 && s >= xs.[j - 1] then
              dp.[j - 1].[k].[s] + dp.[j - 1].[k - 1].[s - xs.[j - 1]]
            else 0L

    let count =
      (seq { 0..n } |> Seq.sumBy (fun k -> dp.[n].[k].[k * a])) - 1L

    printfn "%d" count

    // exit code
    0

Submission Info

Submission Time
Task C - Tak and Cards
User vain0
Language F# (Mono 4.0)
Score 300
Code Size 1203 Byte
Status AC
Exec Time 301 ms
Memory 56260 KB

Compile Error

/imojudge/Main.fs(16,9): warning FS0025: Incomplete pattern matches on this expression. For example, the value '[|_; _; _|]' may indicate a case not covered by the pattern(s).

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 100 / 100
Status
AC × 4
AC × 12
AC × 24
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt AC 79 ms 4052 KB
example_02.txt AC 80 ms 4052 KB
example_03.txt AC 80 ms 4052 KB
example_04.txt AC 84 ms 4948 KB
subtask1_01.txt AC 86 ms 5844 KB
subtask1_02.txt AC 86 ms 5844 KB
subtask1_03.txt AC 87 ms 5844 KB
subtask1_04.txt AC 86 ms 5844 KB
subtask1_05.txt AC 86 ms 5844 KB
subtask1_06.txt AC 80 ms 4052 KB
subtask1_07.txt AC 83 ms 4052 KB
subtask1_08.txt AC 87 ms 5844 KB
subtask1_09.txt AC 85 ms 5460 KB
subtask2_01.txt AC 289 ms 56260 KB
subtask2_02.txt AC 301 ms 56260 KB
subtask2_03.txt AC 279 ms 54220 KB
subtask2_04.txt AC 288 ms 56260 KB
subtask2_05.txt AC 290 ms 56260 KB
subtask2_06.txt AC 297 ms 56260 KB
subtask2_07.txt AC 293 ms 56260 KB
subtask2_08.txt AC 154 ms 22612 KB
subtask2_09.txt AC 154 ms 22612 KB
subtask2_10.txt AC 217 ms 39500 KB
subtask2_11.txt AC 225 ms 42956 KB