結果

問題 No.90 品物の並び替え
ユーザー ichyoichyo
提出日時 2014-12-07 19:19:40
言語 Go
(1.22.1)
結果
AC  
実行時間 491 ms / 5,000 ms
コード長 2,025 bytes
コンパイル時間 11,386 ms
コンパイル使用メモリ 219,620 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-04-18 09:20:00
合計ジャッジ時間 11,979 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 38 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 6 ms
5,376 KB
testcase_05 AC 42 ms
5,376 KB
testcase_06 AC 31 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 491 ms
6,400 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import "fmt"
import "sort"

func compare(a, b []int) int {
	for i := 0; i < len(a) && i < len(b); i++ {
		switch {
		case a[i] > b[i]:
			return 1
		case a[i] < b[i]:
			return -1
		}
	}
	switch {
	case len(a) > len(b):
		return 1
	case len(a) < len(b):
		return -1
	}
	return 0
}

func nextPermutation(seq []int) bool {
	var j int = -1
	var m int = -1

	// Attempt to find the j index, this is the first index where it's value is
	// less than the after it (i.e. seq[j] < seq[j+1])
	for index := len(seq) - 2; index >= 0; index-- {
		if seq[index] < seq[index+1] {
			j = index
			break
		}
	}

	// If no index was found then finish
	if j == -1 {
		return false
	}

	// Find the m index, this is the first index where the value is greater than
	// the value at j
	for index := len(seq) - 1; index > j; index-- {
		if seq[index] > seq[j] {
			m = index
			break
		}
	}

	// Swap the values at the two indexes
	seq[j], seq[m] = seq[m], seq[j]

	// Order all of the values after j
	upper := seq[j+1:]
	sort.Ints(upper)

	for i, v := range upper {
		seq[j+i+1] = v
	}

	return true
}

func Next(seq []int) bool {
	current := make([]int, len(seq), len(seq))
	copy(current, seq)

	for i := 1; i < len(seq); i++ {
		success := nextPermutation(seq)
		if compare(current, seq) != 0 {
			return success
		}
	}

	return false
}

func get(seq []int, val int) int {
	for i, v := range seq {
		if v == val {
			return i
		}
	}
	return -1
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make([]int, m)
	b := make([]int, m)
	c := make([]int, m)
	for i, _ := range a {
		fmt.Scan(&a[i], &b[i], &c[i])
	}

	v := make([]int, n)
	for i, _ := range v {
		v[i] = i
	}

	ans := 0
	for {
		cnt := 0
		for i, _ := range a {
			p := get(v, a[i])
			q := get(v, b[i])
			if p < q {
				cnt += c[i]
			}
		}
		if ans < cnt {
			ans = cnt
		}

		res := Next(v)
		if !res {
			break
		}
	}
	fmt.Println(ans)
}
0