結果
問題 | No.1977 Extracting at Constant Intervals |
ユーザー | 草苺奶昔 |
提出日時 | 2023-02-15 16:31:37 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 2,911 bytes |
コンパイル時間 | 11,608 ms |
コンパイル使用メモリ | 214,184 KB |
実行使用メモリ | 85,268 KB |
最終ジャッジ日時 | 2023-09-25 01:14:53 |
合計ジャッジ時間 | 16,857 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 16 ms
14,132 KB |
testcase_03 | AC | 95 ms
74,872 KB |
testcase_04 | AC | 17 ms
14,140 KB |
testcase_05 | AC | 105 ms
85,268 KB |
testcase_06 | AC | 58 ms
47,720 KB |
testcase_07 | AC | 76 ms
62,292 KB |
testcase_08 | AC | 64 ms
51,872 KB |
testcase_09 | AC | 31 ms
22,688 KB |
testcase_10 | AC | 86 ms
68,552 KB |
testcase_11 | AC | 10 ms
9,964 KB |
testcase_12 | AC | 22 ms
14,160 KB |
testcase_13 | AC | 113 ms
62,304 KB |
testcase_14 | AC | 123 ms
83,176 KB |
testcase_15 | AC | 66 ms
39,392 KB |
testcase_16 | AC | 136 ms
76,932 KB |
testcase_17 | AC | 152 ms
83,188 KB |
testcase_18 | AC | 67 ms
37,320 KB |
testcase_19 | AC | 28 ms
20,608 KB |
testcase_20 | AC | 117 ms
79,012 KB |
testcase_21 | AC | 122 ms
70,684 KB |
testcase_22 | AC | 112 ms
76,932 KB |
testcase_23 | AC | 22 ms
16,376 KB |
testcase_24 | AC | 100 ms
68,544 KB |
testcase_25 | AC | 11 ms
9,964 KB |
testcase_26 | AC | 17 ms
14,128 KB |
testcase_27 | AC | 56 ms
39,396 KB |
testcase_28 | AC | 28 ms
20,608 KB |
testcase_29 | AC | 59 ms
41,472 KB |
testcase_30 | AC | 104 ms
72,764 KB |
testcase_31 | AC | 51 ms
35,240 KB |
testcase_32 | AC | 61 ms
39,404 KB |
ソースコード
package main import ( "bufio" "fmt" "math/bits" "os" ) func main() { // https://yukicoder.me/problems/no/1097 const INF int = int(1e18) const MOD int = 998244353 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, m, l int fmt.Fscan(in, &n, &m, &l) nums := make([]int, n) for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) } db := NewDoubling(n, 1e15) for i := 0; i < n; i++ { j := (i + l) % n db.Add(i, j, nums[j]) } db.Build() res := -INF for i := 0; i < n; i++ { s0 := i s1 := l/n*n + i for s0 >= l { s0 -= n } for s1 >= l { s1 -= n } a0 := (n*m - 1 - s0) / l a1 := (n*m - 1 - s1) / l if s0 >= 0 { _, v := db.Jump(i, a0) res = max(res, v+nums[i]) } if s1 >= 0 { _, v := db.Jump(i, a1) res = max(res, v+nums[i]) } } fmt.Fprintln(out, res) } func max(a, b int) int { if a > b { return a } return b } type E = int // monoidAdd func (*Doubling) e() E { return 0 } func (*Doubling) op(e1, e2 E) E { return e1 + e2 } type Doubling struct { n int log int isPrepared bool to [][]int dp [][]E } func NewDoubling(n, maxStep int) *Doubling { res := &Doubling{} res.n = n res.log = bits.Len(uint(maxStep)) res.to = make([][]int, res.log) res.dp = make([][]E, res.log) for i := 0; i < res.log; i++ { res.to[i] = make([]int, n) res.dp[i] = make([]E, n) for j := 0; j < n; j++ { res.to[i][j] = -1 res.dp[i][j] = res.e() } } return res } // 初始状态(leaves):从 `from` 状态到 `to` 状态,状态的值变为 `value`. // 0 <= from, to < n func (d *Doubling) Add(from, to int, value E) { if d.isPrepared { panic("Doubling is prepared") } if to < -1 || to >= d.n { panic("to is out of range") } d.to[0][from] = to d.dp[0][from] = value } func (d *Doubling) Build() { if d.isPrepared { panic("Doubling is prepared") } d.isPrepared = true for k := 0; k < d.log-1; k++ { for v := 0; v < d.n; v++ { w := d.to[k][v] if w == -1 { d.to[k+1][v] = -1 d.dp[k+1][v] = d.dp[k][v] continue } d.to[k+1][v] = d.to[k][w] d.dp[k+1][v] = d.op(d.dp[k][v], d.dp[k][w]) } } } func (d *Doubling) Jump(from, step int) (to int, res E) { if !d.isPrepared { panic("Doubling is not prepared") } if step >= 1<<d.log { panic("step is over max step") } res = d.e() to = from for k := 0; k < d.log; k++ { if to == -1 { break } if step&(1<<k) != 0 { res = d.op(res, d.dp[k][to]) to = d.to[k][to] } } return } func (d *Doubling) MaxStep(from int, check func(e E) bool) int { if !d.isPrepared { panic("Doubling is not prepared") } res := d.e() step := 0 if !check(res) { return 0 } for k := d.log - 1; k >= 0; k-- { to := d.to[k][from] next := d.op(res, d.dp[k][from]) if check(next) { step |= 1 << k from = to res = next } } return step }