Submission #3388658
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; ans: var seq[int]) = let n = a.len() 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()] 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] var slideMax = newSeq[int](n + 1) for i in 1..<k: dp[i - 1].buildSlideMaximum(m, slideMax) 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 | 700 |
Code Size | 3670 Byte |
Status | AC |
Exec Time | 988 ms |
Memory | 477548 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 (24628 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 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 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 | 96 ms | 50172 KB |
subtask_1_3.txt | AC | 968 ms | 475496 KB |
subtask_1_4.txt | AC | 7 ms | 4348 KB |
subtask_1_5.txt | AC | 34 ms | 18304 KB |
subtask_1_6.txt | AC | 2 ms | 2172 KB |
subtask_1_7.txt | AC | 337 ms | 161900 KB |
subtask_1_8.txt | AC | 969 ms | 475500 KB |
subtask_1_9.txt | AC | 5 ms | 3708 KB |
subtask_2_1.txt | AC | 1 ms | 1532 KB |
subtask_2_2.txt | AC | 1 ms | 1404 KB |
subtask_2_3.txt | AC | 1 ms | 1532 KB |
subtask_2_4.txt | AC | 1 ms | 1404 KB |
subtask_2_5.txt | AC | 1 ms | 1276 KB |
subtask_2_6.txt | AC | 1 ms | 1276 KB |
subtask_2_7.txt | AC | 1 ms | 1532 KB |
subtask_2_8.txt | AC | 1 ms | 1532 KB |
subtask_2_9.txt | AC | 1 ms | 1532 KB |
subtask_3_1.txt | AC | 115 ms | 52072 KB |
subtask_3_2.txt | AC | 115 ms | 52076 KB |
subtask_3_3.txt | AC | 112 ms | 50536 KB |
subtask_3_4.txt | AC | 92 ms | 41708 KB |
subtask_3_5.txt | AC | 6 ms | 4220 KB |
subtask_3_6.txt | AC | 67 ms | 28520 KB |
subtask_3_7.txt | AC | 115 ms | 52072 KB |
subtask_3_8.txt | AC | 12 ms | 6652 KB |
subtask_3_9.txt | AC | 115 ms | 52072 KB |
subtask_4_1.txt | AC | 970 ms | 475496 KB |
subtask_4_10.txt | AC | 839 ms | 475496 KB |
subtask_4_11.txt | AC | 988 ms | 475500 KB |
subtask_4_12.txt | AC | 982 ms | 475500 KB |
subtask_4_13.txt | AC | 977 ms | 475500 KB |
subtask_4_2.txt | AC | 976 ms | 476140 KB |
subtask_4_3.txt | AC | 968 ms | 475500 KB |
subtask_4_4.txt | AC | 969 ms | 477548 KB |
subtask_4_5.txt | AC | 822 ms | 403308 KB |
subtask_4_6.txt | AC | 92 ms | 41068 KB |
subtask_4_7.txt | AC | 520 ms | 252780 KB |
subtask_4_8.txt | AC | 955 ms | 468204 KB |
subtask_4_9.txt | AC | 438 ms | 212716 KB |