Submission #659085

#	Time	Username	Problem	Language	Result	Execution time	Memory
659085		kstew16	앱 (KOI13_app)	Kotlin (JVM)	6.30 / 21	171 ms	17032 KiB

app

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main():Unit = with(BufferedReader(InputStreamReader(System.`in`))){
    val (n,m) = readLine().split(" ").map{it.toInt()}
    // dp[i] i 의 재실행 비용을 통해 확보할 수 있는 최대 메모리
    val dp = IntArray(10001){0}
    data class Process(val memory:Int,val removeCost:Int):Comparable<Process>{
        override fun compareTo(other: Process): Int {
            return when{
                this.removeCost==0 && other.removeCost==0 ->{
                    when{
                        this.memory>other.memory -> -1
                        else -> 1
                    }
                }
                this.removeCost == 0 && other.removeCost!=0 -> -1
                this.removeCost!= 0 && other.removeCost==0 -> 1
                else ->{
                    val a = this.memory/this.removeCost
                    val b = other.memory/other.removeCost
                    when{
                        a>b -> -1
                        else -> 1
                    }
                }
            }
        }
    }

    var st = StringTokenizer(readLine())
    val memoryArr = IntArray(n){st.nextToken().toInt()}
    st = StringTokenizer(readLine())
    val costArr = IntArray(n){st.nextToken().toInt()}
    val processes = Array(n){
        Process(memoryArr[it],costArr[it])
    }.sorted()
    val visited = BooleanArray(n){false}
    for(i in 0 until n){
        if(processes[i].removeCost==0) {
            dp[0] += processes[i].memory
            visited[i] = true
        }
    }
    var minCost = Int.MAX_VALUE
    fun killProcess(i:Int,memoryGot:Int,cost:Int){
        dp[cost] = memoryGot
        if(memoryGot>=m){
            minCost = cost.coerceAtMost(minCost)
            return
        }
        for(next in i+1 until n){
            if(!visited[next]){
                visited[next] = true
                val nextCost = cost + processes[next].removeCost
                if(nextCost<minCost && dp[nextCost]==0)
                    killProcess(next,memoryGot+processes[next].memory,nextCost)
                visited[next] = false
            }
        }
    }
    killProcess(-1,dp[0],0)
    print(minCost)
}

• Subtask 1: 0 / 3.15
• Subtask 2: 3.15 / 3.15
• Subtask 3: 3.15 / 3.15
• Subtask 4: 0 / 3.15
• Subtask 5: 0 / 3.15
• Subtask 6: 0 / 3.15
• Subtask 7: 0 / 2.1