Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import com.sun.org.apache.xml.internal.utils.IntStack
- import java.io.*
- import java.util.*
- class FastIO(private val inp: InputStream, private val out: OutputStream) : PrintWriter(out, false)
- {
- private val reader = BufferedReader(InputStreamReader(inp))
- private var tokenizer = StringTokenizer("")
- fun get() : String?
- {
- while (!tokenizer.hasMoreTokens())
- {
- val s = reader.readLine() ?: return null
- tokenizer = StringTokenizer(s)
- }
- return tokenizer.nextToken()
- }
- fun getWord() : String = get()!!
- fun getInt() : Int = getWord().toInt()
- fun getLong() : Long = getWord().toLong()
- fun getDouble() : Double = getWord().toDouble()
- fun getLine() : String?
- {
- tokenizer = StringTokenizer("")
- return reader.readLine()
- }
- }
- fun main(args: Array<String>)
- {
- FastIO(System.`in`, System.out).use {
- main(it)
- }
- }
- fun main(io: FastIO)
- {
- val n = io.getInt()
- val m = io.getInt()
- val am = IntArray(n, {io.getInt()})
- val ac = IntArray(n, {io.getInt()})
- val d = Array(n, {IntArray(m + 1, {-1})})
- val p = Array(n, {IntArray(m + 1, {-1})})
- d[0] = 0
- // Перебор предметов
- for (j in 0 until n)
- {
- // Перебор положения предмета в массе
- for (i in m - am[j] downTo 0)
- {
- if (d[i] == -1) continue
- if (i + am[j] > m) continue
- if (d[i + am[j]] < d[i] + ac[j])
- {
- d[i + am[j]] = d[i] + ac[j]
- p[i + am[j]] = j
- }
- }
- }
- var maxV = 0
- var maxId = 0
- for (i in 0 until m)
- {
- if (maxV < d[i])
- {
- maxV = d[i]
- maxId = i
- }
- }
- val result = IntArray(n)
- var count = 0
- var cM = maxId
- var cI = p[maxId]
- while (cI >= 0)
- {
- result[count] = cI + 1
- count++
- cM -= am[cI]
- cI = p[cM]
- }
- io.println(count)
- for (i in count - 1 downTo 0)
- {
- io.print(result[i])
- io.print(' ')
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement