oj.uz

Submission #659085

# Submission time Handle Problem Language Result Execution time Memory
659085 2022-11-16T12:35:49 Z kstew16 앱 (KOI13_app) Kotlin
6.3 / 21
 171 ms 17032 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()}
    // 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

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16900 KB Output is correct
2 Correct 140 ms 16480 KB Output is correct
3 Incorrect 137 ms 16720 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 136 ms 16464 KB Output is correct
2 Correct 154 ms 16444 KB Output is correct
3 Correct 134 ms 16564 KB Output is correct
4 Correct 139 ms 16652 KB Output is correct
5 Correct 143 ms 16588 KB Output is correct

Subtask #3
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 140 ms 16576 KB Output is correct
2 Correct 136 ms 16848 KB Output is correct
3 Correct 157 ms 16576 KB Output is correct
4 Correct 155 ms 16704 KB Output is correct
5 Correct 146 ms 16368 KB Output is correct
6 Correct 167 ms 16776 KB Output is correct

Subtask #4
0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16624 KB Output is correct
2 Correct 157 ms 16800 KB Output is correct
3 Correct 151 ms 17032 KB Output is correct
4 Correct 147 ms 16768 KB Output is correct
5 Incorrect 156 ms 16384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 157 ms 16684 KB Output is correct
2 Incorrect 158 ms 16644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 153 ms 16684 KB Output is correct
2 Incorrect 171 ms 16760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 2.1

# Verdict Execution time Memory Grader output
1 Correct 150 ms 16628 KB Output is correct
2 Incorrect 155 ms 16600 KB Output isn't correct
3 Halted 0 ms 0 KB -