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<= 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 }