結果

問題 No.1890 Many Sequences Sum Queries
ユーザー Daiki HirabayashiDaiki Hirabayashi
提出日時 2023-09-26 22:11:20
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 787 ms / 2,000 ms
コード長 1,429 bytes
コンパイル時間 16,333 ms
コンパイル使用メモリ 447,464 KB
実行使用メモリ 85,032 KB
最終ジャッジ日時 2024-07-19 15:58:55
合計ジャッジ時間 27,860 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 651 ms
79,052 KB
testcase_01 AC 787 ms
85,032 KB
testcase_02 AC 332 ms
60,188 KB
testcase_03 AC 320 ms
60,532 KB
testcase_04 AC 324 ms
60,484 KB
testcase_05 AC 318 ms
60,432 KB
testcase_06 AC 348 ms
62,284 KB
testcase_07 AC 607 ms
72,120 KB
testcase_08 AC 552 ms
69,764 KB
testcase_09 AC 555 ms
69,852 KB
testcase_10 AC 650 ms
79,964 KB
testcase_11 AC 635 ms
73,884 KB
testcase_12 AC 642 ms
75,708 KB
testcase_13 AC 652 ms
76,928 KB
testcase_14 AC 608 ms
72,172 KB
testcase_15 AC 324 ms
60,472 KB
testcase_16 AC 324 ms
60,520 KB
testcase_17 AC 311 ms
57,044 KB
testcase_18 AC 325 ms
60,420 KB
testcase_19 AC 331 ms
60,304 KB
testcase_20 AC 323 ms
60,404 KB
testcase_21 AC 324 ms
60,336 KB
testcase_22 AC 329 ms
60,364 KB
testcase_23 AC 322 ms
60,344 KB
testcase_24 AC 326 ms
60,176 KB
testcase_25 AC 306 ms
57,012 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter

fun main() {
    val (n, q) = readln().split(" ").map { it.toInt() }
    val a = readln().split(" ").map { it.toInt() }.toIntArray()
    val s = Array(q) {
        readln().toInt()
    }

    val pList = (0 until n).map { it ->
        (1..a[it]).map { it.toLong() }
        .let {
            P(it.size, it.sum(), cumulativeSum(it))
        }
    }
    val wholeSum = pList.sumOf { it.sum }

    val out = PrintWriter(System.out)
    for(i in 0 until q) {
        if(s[i] > wholeSum) {
            out.println(-1)
            continue
        }

        var sum = 0L
        var sizeSum = 0L
        for(j in pList.indices) {
            val p = pList[j]

            sizeSum += p.size
            sum += p.sum

            if(sum == s[i].toLong()) {
                out.println(sizeSum)
                break
            } else if(sum > s[i]) {
                sizeSum -= p.size
                sum -= p.sum

                val tmp = p.cumulativeSum.binarySearch(s[i] - sum)
                val index = if(tmp < 0) -(tmp + 1) else tmp

                out.println(sizeSum + index)
                break
            }
        }
    }

    out.flush()
}

data class P(
    val size: Int,
    val sum: Long,
    val cumulativeSum: LongArray,
)

fun cumulativeSum(a: List<Long>): LongArray {
    val s = LongArray(a.size + 1)
    for(i in a.indices) {
        s[i+1] = s[i] + a[i]
    }
    return s
}
0