結果

問題 No.90 品物の並び替え
ユーザー yukirin
提出日時 2016-02-16 04:56:58
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,154 bytes
コンパイル時間 12,211 ms
コンパイル使用メモリ 236,836 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-10 22:11:11
合計ジャッジ時間 12,921 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
)
var sc = bufio.NewScanner(os.Stdin)
var rdr = bufio.NewReaderSize(os.Stdin, 1000000)
func main() {
    sc.Split(bufio.ScanWords)
    n, m := uint(nextInt()), nextInt()
    table := make([][]int, n)
    for i := range table {
        table[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        table[nextInt()][nextInt()] = nextInt()
    }
    dp := make([]int, 1<<n)
    for i := 0; i < 1<<n; i++ {
        for j := uint(0); j < n; j++ {
            if i&(1<<j) != 0 {
                continue
            }
            nextI := i | 1<<j
            score := dp[i]
            for k := uint(0); k < n; k++ {
                if i&(1<<k) == 0 {
                    continue
                }
                score += table[k][j]
            }
            if score > dp[nextI] {
                dp[nextI] = score
            }
        }
    }
    fmt.Println(dp[1<<n-1])
}
func nextLine() string {
    sc.Scan()
    return sc.Text()
}
func nextInt() int {
    i, _ := strconv.Atoi(nextLine())
    return i
}
func nextInt64() int64 {
    i, _ := strconv.ParseInt(nextLine(), 10, 64)
    return i
}
func nextUint64() uint64 {
    i, _ := strconv.ParseUint(nextLine(), 10, 64)
    return i
}
func nextFloat() float64 {
    f, _ := strconv.ParseFloat(nextLine(), 64)
    return f
}
func readLine() string {
    buf := make([]byte, 0, 1000000)
    for {
        l, p, e := rdr.ReadLine()
        if e != nil {
            panic(e)
        }
        buf = append(buf, l...)
        if !p {
            break
        }
    }
    return string(buf)
}
func factor(n uint64) []uint64 {
    if n <= 1 {
        return []uint64{n}
    }
    ps := make([]uint64, 0, 100)
    for i := uint64(2); i*i <= n; i++ {
        for n%i == 0 {
            n /= i
            ps = append(ps, i)
        }
    }
    if n > 1 {
        ps = append(ps, n)
    }
    return ps
}
func gcd(a, b uint64) uint64 {
    for ; b != 0; b, a = a%b, b {
    }
    return a
}
func exGcd(x, y int64) (a, b, c int64) {
    if x <= 0 || y <= 0 {
        return
    }
    r0, r1 := x, y
    a0, a1 := int64(1), int64(0)
    b0, b1 := int64(0), int64(1)
    for r1 > 0 {
        q1, r2 := r0/r1, r0%r1
        a2, b2 := a0-q1*a1, b0-q1*b1
        r0, r1 = r1, r2
        a0, a1 = a1, a2
        b0, b1 = b1, b2
    }
    a, b, c = a0, b0, r0
    return
}
func chinese(a1, m1, a2, m2 int64) int64 {
    a, _, c := exGcd(m1, m2)
    if c != 1 {
        return -1
    }
    x := a1 + (a2-a1)*a*m1
    for x < 0 {
        x += m1 * m2
    }
    return x
}
func lcm(a, b uint64) uint64 {
    return (a * b) / gcd(a, b)
}
func round(f float64, place int) float64 {
    shift := math.Pow10(place)
    return math.Floor(f*shift+.5) / shift
}
func round1(f float64) float64 {
    return math.Floor(f + .5)
}
func bitCount(n int64) int64 {
    c := int64(0)
    for i := uint(0); i < 64; i++ {
        if n>>i&1 == 1 {
            c++
        }
    }
    return c
}
func powExp(n, e uint64) uint64 {
    a := uint64(1)
    for e > 0 {
        if e&1 == 1 {
            a *= n
        }
        n *= n
        e >>= 1
    }
    return a
}
func powMod(n, e, mod uint64) uint64 {
    a := uint64(1)
    for e > 0 {
        if e&1 == 1 {
            a *= n
            a %= mod
        }
        n *= n
        n %= mod
        e >>= 1
    }
    return a % mod
}
type priorityQ []int
func (h priorityQ) Len() int {
    return len(h)
}
func (h priorityQ) Less(i, j int) bool {
    return h[i] < h[j]
}
func (h priorityQ) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h *priorityQ) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *priorityQ) Pop() interface{} {
    x := (*h)[len(*h)-1]
    *h = (*h)[0 : len(*h)-1]
    return x
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0