Submission #3388647


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](10^5)

# [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

Submission Time
Task A - Struck Out
User somq14
Language Nim (0.13.0)
Score 500
Code Size 3674 Byte
Status MLE
Exec Time 1415 ms
Memory 578924 KB

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.185 sec total; 24.245MB; Release Build) [SuccessX]

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 0 / 100 200 / 200 300 / 300 0 / 100
Status
AC × 3
AC × 8
MLE × 2
AC × 12
AC × 21
AC × 34
MLE × 12
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
subtask3 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 1276 KB
sample_2.txt AC 1 ms 1276 KB
sample_3.txt AC 1 ms 1276 KB
subtask_1_1.txt AC 1 ms 1404 KB
subtask_1_2.txt AC 142 ms 67580 KB
subtask_1_3.txt MLE 1401 ms 578248 KB
subtask_1_4.txt AC 8 ms 4476 KB
subtask_1_5.txt AC 42 ms 19840 KB
subtask_1_6.txt AC 3 ms 2684 KB
subtask_1_7.txt AC 490 ms 289644 KB
subtask_1_8.txt MLE 1403 ms 578220 KB
subtask_1_9.txt AC 6 ms 4220 KB
subtask_2_1.txt AC 2 ms 1788 KB
subtask_2_2.txt AC 1 ms 1532 KB
subtask_2_3.txt AC 1 ms 1660 KB
subtask_2_4.txt AC 1 ms 1532 KB
subtask_2_5.txt AC 1 ms 1404 KB
subtask_2_6.txt AC 1 ms 1276 KB
subtask_2_7.txt AC 2 ms 1788 KB
subtask_2_8.txt AC 2 ms 1788 KB
subtask_2_9.txt AC 2 ms 1660 KB
subtask_3_1.txt AC 159 ms 73288 KB
subtask_3_2.txt AC 159 ms 73292 KB
subtask_3_3.txt AC 154 ms 73192 KB
subtask_3_4.txt AC 128 ms 71148 KB
subtask_3_5.txt AC 8 ms 4604 KB
subtask_3_6.txt AC 87 ms 37224 KB
subtask_3_7.txt AC 159 ms 73288 KB
subtask_3_8.txt AC 16 ms 8828 KB
subtask_3_9.txt AC 159 ms 73288 KB
subtask_4_1.txt MLE 1403 ms 578248 KB
subtask_4_10.txt MLE 1280 ms 578152 KB
subtask_4_11.txt MLE 1413 ms 578220 KB
subtask_4_12.txt MLE 1415 ms 578220 KB
subtask_4_13.txt MLE 1408 ms 578220 KB
subtask_4_2.txt MLE 1404 ms 578924 KB
subtask_4_3.txt MLE 1402 ms 578156 KB
subtask_4_4.txt MLE 1403 ms 578220 KB
subtask_4_5.txt MLE 1193 ms 578188 KB
subtask_4_6.txt AC 127 ms 73196 KB
subtask_4_7.txt AC 753 ms 289708 KB
subtask_4_8.txt MLE 1383 ms 569324 KB
subtask_4_9.txt AC 634 ms 290380 KB