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