Submission #3388638

---

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]
  cap: int
  siz: int
  s: int
  t: int

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

proc len[T](this: Deque[T]): int = this.siz

proc ensureCapacity[T](this: var Deque[T]) =
  if this.siz < this.cap - 1:
    return

  var aa = newSeq[int](this.cap * 2)
  for i in 0..<this.siz:
    aa[i] = this.a[(this.s + i) and (this.cap - 1)]

  this.a = aa
  this.cap = this.cap * 2
  this.siz = this.siz
  this.s = 0
  this.t = this.siz

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

proc addLast[T](this: var Deque[T]; e: T) =
  this.ensureCapacity()
  this.a[this.t] = e
  this.t = (this.t + 1) and (this.cap - 1)
  this.siz += 1

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

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

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

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

proc clear[T](this: var Deque[T]) =
  this.s = 0
  this.t = 0
  this.siz = 0

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

var deq = initDeque[int]()

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

  deq.clear()
  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 j in 0..<n:
    dp[0][j] = (0 + 1) * a[j]

  for i in 1..<k:
    let slideMax = dp[i - 1].buildSlideMaximum(m)
    dp[i].fill(-INF)
    for j in i..<n:
      if slideMax[j] == -INF:
        continue
      dp[i][j] = slideMax[j] + (i + 1) * a[j]

  var ans = -1
  for j in 0..<n:
    ans = max(ans, dp[k - 1][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(63, 6) Hint: 'Main.addFirst(this: var Deque[addFirst.T], e: T)' is declared but not used [XDeclaredButNotUsed]
Hint:  [Link]
Hint: operation successful (24629 lines compiled; 2.193 sec total; 24.245MB; Release Build) [SuccessX]

Judge Result