結果

問題 No.90 品物の並び替え
ユーザー seiichi
提出日時 2021-01-06 15:55:08
言語 Go
(1.23.4)
結果
AC  
実行時間 997 ms / 5,000 ms
コード長 2,217 bytes
コンパイル時間 13,305 ms
コンパイル使用メモリ 221,548 KB
実行使用メモリ 55,040 KB
最終ジャッジ日時 2024-11-07 01:29:17
合計ジャッジ時間 15,162 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
"fmt"
"strconv"
)
func scan() (N int, M int, scoreMap map[string]int) {
scoreMap = map[string]int{}
fmt.Scan(&N, &M)
for i := 0; i < M; i++ {
var item1, item2 string
var score int
fmt.Scan(&item1, &item2, &score)
key := item1 + "," + item2
scoreMap[key] = score
}
return
}
func permutaions(arr []int) (res [][]int) {
var helper func([]int, int)
helper = func(arr []int, n int) {
if n == 1 {
tmp := make([]int, len(arr))
copy(tmp, arr)
res = append(res, tmp)
} else {
for i := 0; i < n; i++ {
helper(arr, n-1)
if n%2 == 1 {
tmp := arr[i]
arr[i] = arr[n-1]
arr[n-1] = tmp
} else {
tmp := arr[0]
arr[0] = arr[n-1]
arr[n-1] = tmp
}
}
}
}
helper(arr, len(arr))
return res
}
func main() {
N, _, scoreMap := scan()
// N, _, scoreMap := 4, 9, map[string]int{
// "0,1": 1,
// "0,2": 2,
// "0,3": 3,
// "1,2": 4,
// "1,3": 5,
// "2,3": 6,
// "3,2": 100,
// "2,1": 100,
// "1,0": 100,
// }
// N, _, scoreMap := 8, 4, map[string]int{
// "0,1": 227,
// "0,2": 5525,
// "0,4": 9497,
// "0,5": 4472,
// "0,6": 7066,
// "1,0": 2440,
// "1,2": 181,
// "1,3": 1277,
// "1,5": 3233,
// "1,6": 6134,
// "1,7": 5211,
// "2,0": 7250,
// "2,4": 1445,
// "2,5": 8823,
// "2,7": 3310,
// "3,0": 3114,
// "3,1": 5979,
// "3,2": 6712,
// "3,5": 848,
// "3,6": 9264,
// "3,7": 4941,
// "4,0": 5479,
// "4,3": 5900,
// "4,5": 1677,
// "4,6": 7070,
// "4,7": 432,
// "5,0": 8783,
// "5,1": 7180,
// "5,4": 3333,
// "5,6": 4513,
// "5,7": 7044,
// "6,0": 1823,
// "6,5": 2551,
// "6,7": 4808,
// "7,0": 8413,
// "7,1": 125,
// "7,2": 3497,
// "7,3": 4161,
// "7,5": 598,
// "7,6": 6403,
// }
var items []int
for i := 0; i < N; i++ {
items = append(items, i)
}
perms := permutaions(items)
var maxScore int
for _, per := range perms {
tmpMaxScore := 0
for i := 0; i < len(per)-1; i++ {
for j := i + 1; j < len(per); j++ {
key := strconv.Itoa(per[i]) + "," + strconv.Itoa(per[j])
tmpMaxScore += scoreMap[key]
}
}
if tmpMaxScore > maxScore {
maxScore = tmpMaxScore
}
}
fmt.Print(maxScore)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0