結果

問題 No.15 カタログショッピング
コンテスト
ユーザー バカらっく
提出日時 2019-08-31 21:25:14
言語 Kotlin
(2.1.0)
結果
TLE  
実行時間 -
コード長 1,573 bytes
コンパイル時間 13,511 ms
コンパイル使用メモリ 447,728 KB
実行使用メモリ 369,892 KB
最終ジャッジ日時 2024-11-25 08:08:45
合計ジャッジ時間 48,595 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:3:10: warning: parameter 'args' is never used
fun main(args: Array<String>) {
         ^
Main.kt:36:38: warning: 'sumBy((T) -> Int): Int' is deprecated. Use sumOf instead.
    if(subTotal + itemList.drop(idx).sumBy { it.value } < total) {
                                     ^

ソースコード

diff # 

import java.lang.StringBuilder

fun main(args: Array<String>) {
    val(n,s) = readLine()!!.trim().split(" ").map { it.toInt() }
    total = s
    for(i in 1..n) {
        itemList.add(Item(i-1, readLine()!!.toInt()))
    }
    itemList.sortByDescending { it.value }
    val ans = getAns(0, 0).sortedDescending()
    ans.forEach { println(convAns(it)) }
}

fun convAns(num:Int):String {
    val ans = StringBuilder()
    for(i in itemList.indices) {
        val key = 1 shl (itemList.lastIndex - i)
        if(num and key > 0) {
            ans.append(" ")
            ans.append(i + 1)
        }
    }
    return ans.toString().substring(1)
}

var total = 0
class Item(val index:Int, val value:Int)
val itemList = mutableListOf<Item>()

val dic = mutableMapOf<Int, MutableMap<Int, List<Int>>>()

fun getAns(idx:Int, subTotal:Int):List<Int> {
    if(subTotal > total) {
        return mutableListOf()
    }
    if(subTotal + itemList.drop(idx).sumBy { it.value } < total) {
        return mutableListOf()
    }
    if(subTotal == total) {
        return mutableListOf(0)
    }
    if(idx > itemList.lastIndex) {
        return mutableListOf()
    }
    if(!dic.containsKey(idx)) {
        dic[idx] = mutableMapOf()
    }
    dic[idx]!![subTotal]?.let { return it }

    val ans = mutableListOf<Int>()
    val ret1 = getAns(idx + 1, subTotal + itemList[idx].value)
    val ret2 = getAns(idx + 1, subTotal)
    val key = 1 shl (itemList.lastIndex - itemList[idx].index)
    ans.addAll(ret1.map { it + key })
    ans.addAll(ret2)
    dic[idx]!![subTotal]= ans
    return ans
}
0