結果

問題 No.385 カップ麺生活
ユーザー yuki2006
提出日時 2016-06-29 14:16:52
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,255 bytes
コンパイル時間 9,747 ms
コンパイル使用メモリ 228,436 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-04 22:22:03
合計ジャッジ時間 10,816 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "fmt"
)
func getSieves(N int) []int {
    field := make([]bool, N + 1)
    sieves := make([]int, 0)
    for i := 2; i <= N; i++ {
        if !field[i] {
            for k := i * i; k <= N; k += i {
                field[k] = true
            }
            sieves = append(sieves, i)
        }
    }
    return sieves
}
func main() {
    var M, N int
    fmt.Scan(&M, &N)
    C := make([]int, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&C[i])
    }
    dp := make([]int, M + 1)
    fillInt(dp, -1)
    dp[M] = 0
    for i := 0; i < N; i++ {
        for l := M; l >= C[i]; l-- {
            if dp[l] >= 0 {
                dp[l - C[i]] = max(dp[l - C[i]], dp[l] + 1)
            }
        }
    }
    result := 0
    // 素数の場合 金欠チャンスで初期所持金に戻せる
    // つまりdp[number]の回数にもう一度来れる
    // 金欠チャンスは、するかしないかの選択ができるが、初期所持金に戻せるため
    // どのタイミングにしても回数の加算の影響が出ない。
    for _, number := range getSieves(M) {
        if dp[number] >= 0 {
            result += dp[number]
        }
    }
    mx := 0
    for i := 0; i <= M; i++ {
        mx = max(mx, dp[i])
    }
    result += mx
    fmt.Println(result)
}
func fillInt(arr []int, v int) {
    for i := 0; i < len(arr); i++ {
        arr[i] = v
    }
}
func max(a int, b int) int {
    if a < b {
        return b
    }
    return a
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0