結果

問題 No.21 平均の差
ユーザー kat0rik
提出日時 2020-01-16 14:02:03
言語 Go
(1.23.4)
結果
AC  
実行時間 3,004 ms / 5,000 ms
コード長 1,046 bytes
コンパイル時間 12,419 ms
コンパイル使用メモリ 224,464 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 17:06:59
合計ジャッジ時間 16,471 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

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