結果

問題 No.21 平均の差
ユーザー kat0rikkat0rik
提出日時 2020-01-16 14:02:03
言語 Go
(1.22.1)
結果
AC  
実行時間 3,082 ms / 5,000 ms
コード長 1,046 bytes
コンパイル時間 10,116 ms
コンパイル使用メモリ 212,252 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-05 21:47:47
合計ジャッジ時間 14,316 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

package main

import (
	"fmt"
	"math"
)

var tot, k int
var n, sums, nums []int
var maxdiff float64
var ans int

func max(a, b float64) float64 {
	if a > b {
		return a
	}
	return b
}

func min(a, b float64) float64 {
	if a < b {
		return a
	}
	return b
}

func dfs(step int, sums, nums []int) {
	// fmt.Printf("dfs(%d, %v, %v) en:\n", step, sums, nums)
	if step == tot {
		for i := 0; i < k; i++ {
			if sums[i] == 0 {
				return
			}
		}
		maxavg := 0.0
		minavg := 1000000.0
		for i := 0; i < k; i++ {
			avg := float64(sums[i]) / float64(nums[i])
			maxavg = max(maxavg, avg)
			minavg = min(minavg, avg)
		}
		maxdiff = max(maxdiff, maxavg-minavg)
		if int(math.Ceil(maxdiff)) > ans {
			ans = int(math.Ceil(maxdiff))
		}
		return
	}
	for i := 0; i < k; i++ {
		sums[i] += n[step]
		nums[i]++
		dfs(step+1, sums, nums)
		sums[i] -= n[step]
		nums[i]--
	}
}

func main() {
	fmt.Scan(&tot, &k)
	nums = make([]int, k)
	sums = make([]int, k)
	n = make([]int, tot)
	for i := range n {
		fmt.Scan(&n[i])
	}
	dfs(0, nums, sums)
	fmt.Println(ans)
}
0