oj.uz

Submission #659089

# Submission time Handle Problem Language Result Execution time Memory
659089 2022-11-16T13:07:58 Z kstew16 앱 (KOI13_app) Kotlin
21 / 21
 192 ms 18732 KB 
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

# Verdict Execution time Memory Grader output
1 Correct 153 ms 14524 KB Output is correct
2 Correct 149 ms 14892 KB Output is correct
3 Correct 167 ms 14924 KB Output is correct
4 Correct 157 ms 14644 KB Output is correct
5 Correct 125 ms 14396 KB Output is correct
6 Correct 146 ms 14640 KB Output is correct

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 138 ms 14248 KB Output is correct
2 Correct 173 ms 14612 KB Output is correct
3 Correct 149 ms 14748 KB Output is correct
4 Correct 147 ms 14756 KB Output is correct
5 Correct 172 ms 14876 KB Output is correct

Subtask #3
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 146 ms 16236 KB Output is correct
2 Correct 144 ms 14728 KB Output is correct
3 Correct 148 ms 16300 KB Output is correct
4 Correct 186 ms 16572 KB Output is correct
5 Correct 153 ms 16236 KB Output is correct
6 Correct 177 ms 16556 KB Output is correct

Subtask #4
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 192 ms 15056 KB Output is correct
2 Correct 147 ms 16372 KB Output is correct
3 Correct 173 ms 16160 KB Output is correct
4 Correct 166 ms 16424 KB Output is correct
5 Correct 192 ms 16372 KB Output is correct
6 Correct 145 ms 16196 KB Output is correct

Subtask #5
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 172 ms 18564 KB Output is correct
2 Correct 190 ms 18684 KB Output is correct
3 Correct 153 ms 18456 KB Output is correct
4 Correct 149 ms 18404 KB Output is correct
5 Correct 159 ms 16164 KB Output is correct
6 Correct 173 ms 16304 KB Output is correct

Subtask #6
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 150 ms 18324 KB Output is correct
2 Correct 191 ms 16552 KB Output is correct
3 Correct 166 ms 16516 KB Output is correct
4 Correct 161 ms 18376 KB Output is correct
5 Correct 170 ms 16092 KB Output is correct
6 Correct 170 ms 18732 KB Output is correct

Subtask #7
2.1 / 2.1

# Verdict Execution time Memory Grader output
1 Correct 175 ms 18608 KB Output is correct
2 Correct 159 ms 18352 KB Output is correct
3 Correct 169 ms 18368 KB Output is correct
4 Correct 153 ms 18476 KB Output is correct