Submission #659089

#	Time	Username	Problem	Language	Result	Execution time	Memory
659089		kstew16	앱 (KOI13_app)	Kotlin (JVM)	21 / 21	192 ms	18732 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()}

    var st = StringTokenizer(readLine())
    val memoryArr = IntArray(n){st.nextToken().toInt()}
    st = StringTokenizer(readLine())
    val costArr = IntArray(n){st.nextToken().toInt()}

    // dp[p][i] p번째 프로그램까지 실행해 봤을 때, i 의 재실행 비용을 통해 확보할 수 있는 최대 메모리
    val dp = Array(n){IntArray(10001){0}}.apply{this[0][costArr[0]] = memoryArr[0]}

    for(i in 1 until n){
        val cost = costArr[i]
        val memory = memoryArr[i]
        for(j in 0 until 10001){
            dp[i][j] = dp[i-1][j]
            if(j-cost in 0 until 10001) dp[i][j] = (dp[i-1][j-cost] + memory).coerceAtLeast(dp[i][j])
        }
    }
    for(j in 0 until 10001){
        if(dp[n-1][j]>=m){
            print(j)
            break
        }
    }
}

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