Submission #3388420

---

Source Code Expand

import strutils
import sequtils
import algorithm
import math
import queues
import tables
import sets
import future

const INF* = int(1e18 + 373)

proc readSeq*(): seq[string] = stdin.readLine().strip().split()
proc readSeq*(n: Natural): seq[string] =
  result = newSeq[string](n)
  for i in 0..<n:
    result[i] = stdin.readLine().strip()

proc readInt1*(): int = readSeq().map(parseInt)[0]
proc readInt2*(): (int, int) =
  let a = readSeq().map(parseInt)
  return (a[0], a[1])
proc readInt3*(): (int, int, int) =
  let a = readSeq().map(parseInt)
  return (a[0], a[1], a[2])
proc readInt4*(): (int, int, int, int) =
  let a = readSeq().map(parseInt)
  return (a[0], a[1], a[2], a[3])

type seq2*[T] = seq[seq[T]]
proc newSeq2*[T](n1, n2: Natural): seq2[T] = newSeqWith(n1, newSeq[T](n2))

#------------------------------------------------------------------------------#
type Deque[T] = object
  a: seq[T]
  s: int
  t: int

proc initDeque[T](init: int = 16): Deque[T] =
  result.a = newSeq[T](init)
  result.s = 0
  result.t = 0

proc len[T](this: Deque[T]): int =
  (this.t - this.s + this.a.len()) mod this.a.len()

proc ensureCapacity[T](this: var Deque[T]) =
  let n = this.len()

  if n < this.a.len() - 1:
    return

  var aa = newSeq[int](this.a.len() * 2)
  for i in 0..<n:
    aa[i] = this.a[(this.s + i) mod this.a.len()]

  this.a = aa
  this.s = 0
  this.t = n

proc addFirst[T](this: var Deque[T]; e: T) =
  this.ensureCapacity()
  this.s = (this.s - 1 + this.a.len()) mod this.a.len()
  this.a[this.s] = e

proc addLast[T](this: var Deque[T]; e: T) =
  this.ensureCapacity()
  this.a[this.t] = e
  this.t = (this.t + 1) mod this.a.len()

proc popFirst[T](this: var Deque[T]): T =
  if this.len() <= 0:
    raise newException(IndexError, "Deque Is Empty")
  let res = this.a[this.s]
  this.s = (this.s + 1) mod this.a.len()
  return res

proc popLast[T](this: var Deque[T]): T =
  if this.len() <= 0:
    raise newException(IndexError, "Deque Is Empty")
  this.t = (this.t - 1 + this.a.len()) mod this.a.len()
  return this.a[this.t]

proc peekFirst[T](this: Deque[T]): T =
  if this.len() <= 0:
    raise newException(IndexError, "Deque Is Empty")
  return this.a[this.s]

proc peekLast[T](this: Deque[T]): T =
  if this.len() <= 0:
    raise newException(IndexError, "Deque Is Empty")
  return this.a[(this.t - 1 + this.a.len()) mod this.a.len()]

#------------------------------------------------------------------------------#

# [i - w, i)の範囲の最大値
proc buildSlideMaximum(a: seq[int]; w: int): seq[int] =
  let n = a.len()
  var ans = newSeq[int](n + 1)

  var deq = initDeque[int]()
  for i in 1..n:
    while deq.len() > 0 and a[deq.peekLast()] <= a[i - 1]:
      discard deq.popLast()
    deq.addLast(i - 1)

    while deq.len() > 0 and deq.peekFirst() < i - w:
      discard deq.popFirst()

    ans[i] = a[deq.peekFirst()]

  return ans

proc main() =
  let (n, m, k) = readInt3()
  let a = readSeq().map(parseInt)

  var dp = newSeq2[int](k, n)
  for i in 1..<k:
    dp[i][0] = -INF

  for i in 1..<k:
    for j in 0..<n:
      if dp[i - 1][j] == -INF:
        continue
      dp[i - 1][j] += i * a[j]

    dp[i] = dp[i - 1].buildSlideMaximum(m)

  var ans = -INF
  for j in 0..<n:
    ans = max(ans, dp[k - 1][j] + k * a[j])
  echo ans

main()

Submission Info

Compile Error

Hint: system [Processing]
Hint: Main [Processing]
Hint: strutils [Processing]
Hint: parseutils [Processing]
Hint: sequtils [Processing]
Hint: algorithm [Processing]
Hint: math [Processing]
Hint: times [Processing]
Hint: queues [Processing]
Hint: tables [Processing]
Hint: hashes [Processing]
Hint: etcpriv [Processing]
Hint: sets [Processing]
Hint: os [Processing]
Hint: posix [Processing]
Hint: future [Processing]
Hint: macros [Processing]
Main.nim(60, 6) Hint: 'Main.addFirst(this: var Deque[addFirst.T], e: T)' is declared but not used [XDeclaredButNotUsed]
Hint:  [Link]
Hint: operation successful (24615 lines compiled; 2.232 sec total; 24.245MB; Release Build) [SuccessX]

Judge Result