結果
問題 | No.90 品物の並び替え |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
package mainimport ("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 stringvar score intfmt.Scan(&item1, &item2, &score)key := item1 + "," + item2scoreMap[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 []intfor i := 0; i < N; i++ {items = append(items, i)}perms := permutaions(items)var maxScore intfor _, per := range perms {tmpMaxScore := 0for 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)}