# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
107033 | gs14004 | 서울에서 경산까지 (KOI17_travel) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import kotlin.math.*
import java.util.*
import java.math.*
fun main(args : Array<String>) = with(Scanner(System.`in`)) {
val (n, k) = readLine()!!.trim().split(" ").map{ it.toInt() }
var dp = Array(k + 1) { 0 }
var nxt = Array(k + 1) { -987654321 }
for (i in 0..(n-1)){
val (x1, w1, x2, w2) = readLine()!!.trim().split(" ").map{ it.toInt() }
for(j in 0..k) nxt[j] = -987654321;
for(j in 0..k){
if(j >= x1) nxt[j] = max(nxt[j], dp[j - x1] + w1);
if(j >= x2) nxt[j] = max(nxt[j], dp[j - x2] + w2);
}
for(j in 0..k) dp[j] = nxt[j];
}
println(dp[k])
}