結果
問題 | No.1826 Fruits Collecting |
ユーザー | yudedako |
提出日時 | 2022-01-31 16:08:20 |
言語 | Scala(Beta) (3.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,482 bytes |
コンパイル時間 | 11,058 ms |
コンパイル使用メモリ | 262,244 KB |
実行使用メモリ | 107,112 KB |
最終ジャッジ日時 | 2023-09-02 02:16:31 |
合計ジャッジ時間 | 41,723 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 985 ms
62,660 KB |
testcase_01 | AC | 1,050 ms
63,112 KB |
testcase_02 | AC | 1,050 ms
62,992 KB |
testcase_03 | AC | 1,055 ms
62,920 KB |
testcase_04 | AC | 986 ms
62,664 KB |
testcase_05 | AC | 1,864 ms
78,220 KB |
testcase_06 | TLE | - |
testcase_07 | AC | 1,882 ms
76,312 KB |
testcase_08 | AC | 1,306 ms
63,652 KB |
testcase_09 | TLE | - |
testcase_10 | AC | 1,900 ms
78,608 KB |
testcase_11 | AC | 1,842 ms
79,140 KB |
testcase_12 | AC | 1,557 ms
68,340 KB |
testcase_13 | AC | 1,389 ms
66,524 KB |
testcase_14 | AC | 1,455 ms
66,220 KB |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | AC | 936 ms
62,600 KB |
testcase_26 | AC | 940 ms
62,528 KB |
testcase_27 | AC | 936 ms
62,496 KB |
testcase_28 | AC | 944 ms
62,308 KB |
testcase_29 | AC | 945 ms
62,628 KB |
testcase_30 | AC | 1,591 ms
68,280 KB |
testcase_31 | AC | 1,870 ms
78,172 KB |
testcase_32 | AC | 1,588 ms
70,712 KB |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | AC | 1,504 ms
65,912 KB |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | AC | 1,829 ms
78,832 KB |
testcase_39 | AC | 1,596 ms
78,320 KB |
testcase_40 | AC | 1,708 ms
92,224 KB |
testcase_41 | AC | 1,336 ms
65,600 KB |
testcase_42 | AC | 1,085 ms
63,216 KB |
testcase_43 | AC | 912 ms
62,556 KB |
testcase_44 | AC | 928 ms
62,488 KB |
testcase_45 | AC | 930 ms
62,544 KB |
ソースコード
import scala.collection.mutable import scala.collection.mutable.ArrayBuffer import scala.io.StdIn.* import scala.math.* import scala.reflect.ClassTag import scala.util.chaining.* class BinaryIndexedTree(val size: Int): private val vec = Array.fill(size){0L} def get(position: Int): Long = var result = 0L var pos = position while vec.indices.contains(pos) do result = max(result, vec(pos)) pos -= ~pos & (pos + 1) result def add(position: Int, value: Long): Unit = var pos = position while vec.indices.contains(pos) do vec(pos) = max(vec(pos), value) pos += ~pos & (pos + 1) def getAll(): Long = get(size - 1) extension (array: Array[Int]) def lowerBound(value: Int): Int = var min = 0 var max = array.length while min < max do val mid = (min + max) >>> 1 if array(mid) < value then min = mid + 1 else max = mid max @main def main = val n = readLine().toInt val fruits = Array.fill(n){ val Array(t, x, v) = readLine().split(' ').map(_.toInt) (t, x, v) } val diff = fruits.map{(t, x, _) => t - x}.distinct.sorted val bit = BinaryIndexedTree(diff.length) for (t, x, v) <- fruits.sorted(using Ordering.by[(Int, Int, Int), Int]{(t, x, _) => t + x}.orElseBy{(t, _, _) => t}) do if t >= abs(x) then val di = diff.lowerBound(t - x) val maxValue = bit.get(di) + v bit.add(di, maxValue) val result = bit.getAll() println(result)