結果
問題 |
No.1211 円環はお断り
|
ユーザー |
|
提出日時 | 2025-02-24 02:28:56 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 1,879 bytes |
コンパイル時間 | 11,450 ms |
コンパイル使用メモリ | 236,256 KB |
実行使用メモリ | 10,124 KB |
最終ジャッジ日時 | 2025-02-24 02:29:11 |
合計ジャッジ時間 | 14,223 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
// F - Cake Division // https://atcoder.jp/contests/abc370/tasks/abc370_f // !给定一个环形数组,分成k个非空连续子数组,使得这k个子数组的和的最小值最大,求出最大值.并求出哪些点不能作为第一段的起点. // 1<=k<=n<=10^5 1<=nums[i]<=10^9 package main import ( "bufio" "fmt" "os" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, k int fmt.Fscan(in, &n, &k) nums := make([]int, n) for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) } presum := make([]int, n+1) for i := 0; i < n; i++ { presum[i+1] = presum[i] + nums[i] } check := func(mid int) bool { { // 先求解链上的问题(剪枝) count := 0 left := 0 for right := 0; right < n; right++ { if presum[right+1]-presum[left] >= mid { count++ left = right + 1 } } if count >= k { return true } if count <= k-2 { return false } } next := make([]int, n) right := 0 for left := 0; left < n; left++ { for right < n && presum[right]-presum[left] < mid { right++ } if presum[right]-presum[left] >= mid { next[left] = right } else { next[left] = -1 } } type dpItem struct{ count, next int } dp := make([]dpItem, n+1) dp[n] = dpItem{next: n} for i := n - 1; i >= 0; i-- { if next[i] == -1 { dp[i] = dpItem{next: i} } else { dp[i] = dp[next[i]] dp[i].count++ } } for i := 0; i < n; i++ { count := dp[i].count if count <= k-2 { break } end := dp[i].next if presum[n]-(presum[end]-presum[i]) >= mid { count++ } if count >= k { return true } } return false } left, right := 1, presum[n]/k+1 for left <= right { mid := (left + right) / 2 if check(mid) { left = mid + 1 } else { right = mid - 1 } } fmt.Fprintln(out, right) }