Submission #3388614
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) 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)] #------------------------------------------------------------------------------# # [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](w) 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 | 200 |
Code Size | 3556 Byte |
Status | RE |
Exec Time | 1496 ms |
Memory | 604804 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 (24622 lines compiled; 2.176 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 | 0 / 300 | 0 / 100 | ||||||||||||||||||
Status |
|
|
|
|
|
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 | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 1 ms | 380 KB |
subtask_1_2.txt | AC | 150 ms | 67580 KB |
subtask_1_3.txt | MLE | 1493 ms | 604024 KB |
subtask_1_4.txt | AC | 8 ms | 4604 KB |
subtask_1_5.txt | AC | 41 ms | 20640 KB |
subtask_1_6.txt | AC | 2 ms | 1660 KB |
subtask_1_7.txt | AC | 509 ms | 302936 KB |
subtask_1_8.txt | MLE | 1496 ms | 604048 KB |
subtask_1_9.txt | AC | 6 ms | 4220 KB |
subtask_2_1.txt | AC | 1 ms | 892 KB |
subtask_2_2.txt | AC | 1 ms | 508 KB |
subtask_2_3.txt | AC | 1 ms | 636 KB |
subtask_2_4.txt | AC | 1 ms | 636 KB |
subtask_2_5.txt | AC | 1 ms | 380 KB |
subtask_2_6.txt | AC | 1 ms | 256 KB |
subtask_2_7.txt | AC | 1 ms | 764 KB |
subtask_2_8.txt | AC | 1 ms | 764 KB |
subtask_2_9.txt | AC | 1 ms | 636 KB |
subtask_3_1.txt | AC | 159 ms | 75288 KB |
subtask_3_2.txt | AC | 156 ms | 76360 KB |
subtask_3_3.txt | AC | 151 ms | 76320 KB |
subtask_3_4.txt | AC | 125 ms | 70500 KB |
subtask_3_5.txt | AC | 8 ms | 4400 KB |
subtask_3_6.txt | RE | 50 ms | 31956 KB |
subtask_3_7.txt | AC | 164 ms | 76988 KB |
subtask_3_8.txt | AC | 16 ms | 8828 KB |
subtask_3_9.txt | AC | 156 ms | 77052 KB |
subtask_4_1.txt | MLE | 1422 ms | 602032 KB |
subtask_4_10.txt | MLE | 1273 ms | 586788 KB |
subtask_4_11.txt | MLE | 557 ms | 530244 KB |
subtask_4_12.txt | MLE | 576 ms | 539648 KB |
subtask_4_13.txt | MLE | 1405 ms | 604804 KB |
subtask_4_2.txt | MLE | 1400 ms | 604760 KB |
subtask_4_3.txt | MLE | 1483 ms | 603000 KB |
subtask_4_4.txt | MLE | 1418 ms | 602616 KB |
subtask_4_5.txt | MLE | 1187 ms | 601596 KB |
subtask_4_6.txt | AC | 133 ms | 77164 KB |
subtask_4_7.txt | AC | 744 ms | 302952 KB |
subtask_4_8.txt | MLE | 1404 ms | 593556 KB |
subtask_4_9.txt | AC | 625 ms | 302176 KB |