結果
問題 | No.962 LCPs |
ユーザー | yakamoto |
提出日時 | 2020-01-11 14:25:02 |
言語 | Kotlin (1.9.23) |
結果 |
AC
|
実行時間 | 719 ms / 2,000 ms |
コード長 | 1,625 bytes |
コンパイル時間 | 18,243 ms |
コンパイル使用メモリ | 431,824 KB |
実行使用メモリ | 80,080 KB |
最終ジャッジ日時 | 2023-08-16 10:09:23 |
合計ジャッジ時間 | 54,852 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 314 ms
57,088 KB |
testcase_01 | AC | 310 ms
57,116 KB |
testcase_02 | AC | 341 ms
57,556 KB |
testcase_03 | AC | 342 ms
57,416 KB |
testcase_04 | AC | 329 ms
57,912 KB |
testcase_05 | AC | 330 ms
57,704 KB |
testcase_06 | AC | 321 ms
57,280 KB |
testcase_07 | AC | 333 ms
57,736 KB |
testcase_08 | AC | 344 ms
57,620 KB |
testcase_09 | AC | 333 ms
57,388 KB |
testcase_10 | AC | 331 ms
57,672 KB |
testcase_11 | AC | 319 ms
57,176 KB |
testcase_12 | AC | 310 ms
57,072 KB |
testcase_13 | AC | 312 ms
57,276 KB |
testcase_14 | AC | 318 ms
57,184 KB |
testcase_15 | AC | 312 ms
57,256 KB |
testcase_16 | AC | 320 ms
57,120 KB |
testcase_17 | AC | 664 ms
80,080 KB |
testcase_18 | AC | 546 ms
71,940 KB |
testcase_19 | AC | 540 ms
71,616 KB |
testcase_20 | AC | 519 ms
63,444 KB |
testcase_21 | AC | 516 ms
63,596 KB |
testcase_22 | AC | 512 ms
63,400 KB |
testcase_23 | AC | 535 ms
63,296 KB |
testcase_24 | AC | 505 ms
59,388 KB |
testcase_25 | AC | 504 ms
59,340 KB |
testcase_26 | AC | 513 ms
59,416 KB |
testcase_27 | AC | 559 ms
63,636 KB |
testcase_28 | AC | 522 ms
59,216 KB |
testcase_29 | AC | 539 ms
59,224 KB |
testcase_30 | AC | 573 ms
64,000 KB |
testcase_31 | AC | 592 ms
63,532 KB |
testcase_32 | AC | 512 ms
59,276 KB |
testcase_33 | AC | 615 ms
72,228 KB |
testcase_34 | AC | 540 ms
59,432 KB |
testcase_35 | AC | 540 ms
59,368 KB |
testcase_36 | AC | 543 ms
63,248 KB |
testcase_37 | AC | 554 ms
59,728 KB |
testcase_38 | AC | 588 ms
60,564 KB |
testcase_39 | AC | 543 ms
59,696 KB |
testcase_40 | AC | 582 ms
60,984 KB |
testcase_41 | AC | 554 ms
61,252 KB |
testcase_42 | AC | 574 ms
60,476 KB |
testcase_43 | AC | 579 ms
61,088 KB |
testcase_44 | AC | 577 ms
60,512 KB |
testcase_45 | AC | 577 ms
60,800 KB |
testcase_46 | AC | 574 ms
60,928 KB |
testcase_47 | AC | 472 ms
62,008 KB |
testcase_48 | AC | 474 ms
61,500 KB |
testcase_49 | AC | 467 ms
61,640 KB |
testcase_50 | AC | 475 ms
61,620 KB |
testcase_51 | AC | 417 ms
59,216 KB |
testcase_52 | AC | 416 ms
59,272 KB |
testcase_53 | AC | 472 ms
60,648 KB |
testcase_54 | AC | 472 ms
61,624 KB |
testcase_55 | AC | 494 ms
60,636 KB |
testcase_56 | AC | 470 ms
61,056 KB |
testcase_57 | AC | 499 ms
62,304 KB |
testcase_58 | AC | 504 ms
62,656 KB |
testcase_59 | AC | 503 ms
62,428 KB |
testcase_60 | AC | 516 ms
62,204 KB |
testcase_61 | AC | 506 ms
61,868 KB |
testcase_62 | AC | 511 ms
62,280 KB |
testcase_63 | AC | 636 ms
73,840 KB |
testcase_64 | AC | 420 ms
58,964 KB |
testcase_65 | AC | 719 ms
74,088 KB |
ソースコード
import kotlin.math.min val MOD = 1_000_000_007 fun main() { val (N) = readInts() val S = Array(N){ readLine()!!} val lcps = mutableListOf<Pair<Int, Int>>() for (i in 0 until N - 1) { var l = 0 val mx = min(S[i].length, S[i + 1].length) while(l < mx && S[i][l] == S[i + 1][l]) l++ lcps.add(Pair(i, l)) } lcps.sortBy { it.second } val t = sortedSetOf<Int>() t.add(-1) t.add(N - 1) var ans = 0L S.forEach { ans += it.length } for (lcp in lcps) { val i = lcp.first val l = (i - t.lower(i)!! - 1).toLong() val r = (t.higher(i)!! - i - 1).toLong() var lensum = (l + 1) * (r + 1) * 2 lensum += (l + 1) * r * (r + 1) / 2 lensum += l * (l + 1) / 2 * (r + 1) ans += lensum * lcp.second debug{"l:$l r:$r"} t.add(i) } println(ans) } private val isDebug = try { // なんか本番でエラーでる System.getenv("MY_DEBUG") != null } catch (t: Throwable) { false } private fun readLn() = readLine()!! private fun readInt() = readLn().toInt() private fun readStrings() = readLn().split(" ") private fun readInts() = readStrings().map { it.toInt() }.toIntArray() private fun readLongs() = readStrings().map { it.toLong() }.toLongArray() private inline fun debug(msg: () -> String) { if (isDebug) System.err.println(msg()) } private fun debug(a: LongArray) { debug{a.joinToString(" ")} } private fun debug(a: IntArray) { debug{a.joinToString(" ")} } private fun debug(a: BooleanArray) { debug{a.map{if(it) 1 else 0}.joinToString("")} } private fun debugDim(A: Array<IntArray>) { if (isDebug) { for (a in A) { debug(a) } } }