結果
問題 | No.1826 Fruits Collecting |
ユーザー | yudedako |
提出日時 | 2022-01-31 16:16:38 |
言語 | Kotlin (1.9.23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,490 bytes |
コンパイル時間 | 17,157 ms |
コンパイル使用メモリ | 432,456 KB |
実行使用メモリ | 106,636 KB |
最終ジャッジ日時 | 2023-09-02 02:18:10 |
合計ジャッジ時間 | 70,461 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 350 ms
57,448 KB |
testcase_01 | AC | 409 ms
58,620 KB |
testcase_02 | AC | 405 ms
58,832 KB |
testcase_03 | AC | 437 ms
58,796 KB |
testcase_04 | AC | 356 ms
57,444 KB |
testcase_05 | AC | 1,346 ms
68,668 KB |
testcase_06 | AC | 1,719 ms
74,932 KB |
testcase_07 | AC | 1,488 ms
71,392 KB |
testcase_08 | AC | 564 ms
59,460 KB |
testcase_09 | AC | 1,671 ms
80,152 KB |
testcase_10 | AC | 1,412 ms
75,472 KB |
testcase_11 | AC | 1,393 ms
73,232 KB |
testcase_12 | AC | 826 ms
62,184 KB |
testcase_13 | AC | 688 ms
61,352 KB |
testcase_14 | AC | 771 ms
61,916 KB |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | AC | 1,982 ms
91,240 KB |
testcase_21 | AC | 1,927 ms
103,984 KB |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | AC | 286 ms
55,032 KB |
testcase_26 | AC | 289 ms
53,016 KB |
testcase_27 | AC | 304 ms
57,172 KB |
testcase_28 | AC | 301 ms
57,304 KB |
testcase_29 | AC | 304 ms
57,116 KB |
testcase_30 | AC | 861 ms
64,776 KB |
testcase_31 | AC | 1,369 ms
72,420 KB |
testcase_32 | AC | 970 ms
66,228 KB |
testcase_33 | AC | 1,727 ms
78,496 KB |
testcase_34 | AC | 1,642 ms
77,656 KB |
testcase_35 | AC | 782 ms
61,936 KB |
testcase_36 | AC | 1,625 ms
75,772 KB |
testcase_37 | AC | 1,445 ms
76,020 KB |
testcase_38 | AC | 1,277 ms
71,480 KB |
testcase_39 | AC | 926 ms
74,412 KB |
testcase_40 | AC | 979 ms
76,584 KB |
testcase_41 | AC | 689 ms
61,768 KB |
testcase_42 | AC | 481 ms
59,036 KB |
testcase_43 | AC | 301 ms
57,152 KB |
testcase_44 | AC | 301 ms
57,672 KB |
testcase_45 | AC | 305 ms
57,528 KB |
ソースコード
import kotlin.math.absoluteValue class MaxBit(val size: Int) { private val array = LongArray(size){0} fun get(position: Int): Long { var result = 0L var pos = position while (pos in array.indices) { result = maxOf(result, array[pos]) pos -= pos.inv() and (pos + 1) } return result } fun add(position: Int, value: Long) { var pos = position while (pos in array.indices) { array[pos] = maxOf(array[pos], value) pos += pos.inv() and (pos + 1) } } fun getAll(): Long = get(size - 1) } fun List<Int>.lowerBound(value: Int): Int { var min = 0 var max = size while (min < max) { val mid = (min + max) ushr 1 if (this[mid] < value) { min = mid + 1 }else { max = mid } } return max } fun main() { val n = readLine()!!.toInt() val fruits = List(n){ val (t, x, v) = readLine()!!.split(' ').map(String::toInt) Triple(t, x, v) } val diff = fruits.map { (t, x, _) -> t - x}.distinct().sorted() val bit = MaxBit(diff.size) for ((t, x, v) in fruits.sortedWith(compareBy<Triple<Int, Int, Int>> { (t, x, _) -> t + x}.thenBy { (t, _, _) -> t })) { if (t < x.absoluteValue) continue val di = diff.lowerBound(t - x) val maxValue = bit.get(di) + v bit.add(di, maxValue) } val result = bit.getAll() println(result) }