Advertisement
Guest User

Untitled

a guest
Jul 12th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 2.18 KB | None | 0 0
  1. import com.sun.org.apache.xml.internal.utils.IntStack
  2. import java.io.*
  3. import java.util.*
  4.  
  5. class FastIO(private val inp: InputStream, private val out: OutputStream) : PrintWriter(out, false)
  6. {
  7.     private val reader = BufferedReader(InputStreamReader(inp))
  8.     private var tokenizer = StringTokenizer("")
  9.  
  10.     fun get() : String?
  11.     {
  12.         while (!tokenizer.hasMoreTokens())
  13.         {
  14.             val s = reader.readLine() ?: return null
  15.             tokenizer = StringTokenizer(s)
  16.         }
  17.  
  18.         return tokenizer.nextToken()
  19.     }
  20.  
  21.     fun getWord() : String = get()!!
  22.     fun getInt() : Int = getWord().toInt()
  23.     fun getLong() : Long = getWord().toLong()
  24.     fun getDouble() : Double = getWord().toDouble()
  25.  
  26.     fun getLine() : String?
  27.     {
  28.         tokenizer = StringTokenizer("")
  29.         return reader.readLine()
  30.     }
  31. }
  32.  
  33. fun main(args: Array<String>)
  34. {
  35.     FastIO(System.`in`, System.out).use {
  36.         main(it)
  37.     }
  38. }
  39.  
  40. fun main(io: FastIO)
  41. {
  42.     val n = io.getInt()
  43.     val m = io.getInt()
  44.  
  45.     val am = IntArray(n, {io.getInt()})
  46.     val ac = IntArray(n, {io.getInt()})
  47.  
  48.     val d = Array(n, {IntArray(m + 1, {-1})})
  49.     val p = Array(n, {IntArray(m + 1, {-1})})
  50.  
  51.     d[0] = 0
  52.  
  53.     // Перебор предметов
  54.     for (j in 0 until n)
  55.     {
  56.         // Перебор положения предмета в массе
  57.         for (i in m - am[j] downTo 0)
  58.         {
  59.             if (d[i] == -1) continue
  60.             if (i + am[j] > m) continue
  61.  
  62.             if (d[i + am[j]] < d[i] + ac[j])
  63.             {
  64.                 d[i + am[j]] = d[i] + ac[j]
  65.                 p[i + am[j]] = j
  66.             }
  67.         }
  68.     }
  69.  
  70.     var maxV = 0
  71.     var maxId = 0
  72.  
  73.     for (i in 0 until m)
  74.     {
  75.         if (maxV < d[i])
  76.         {
  77.             maxV = d[i]
  78.             maxId = i
  79.         }
  80.     }
  81.  
  82.     val result = IntArray(n)
  83.     var count = 0
  84.  
  85.     var cM = maxId
  86.     var cI = p[maxId]
  87.  
  88.     while (cI >= 0)
  89.     {
  90.         result[count] = cI + 1
  91.         count++
  92.  
  93.         cM -= am[cI]
  94.         cI = p[cM]
  95.     }
  96.  
  97.     io.println(count)
  98.  
  99.     for (i in count - 1 downTo 0)
  100.     {
  101.         io.print(result[i])
  102.         io.print(' ')
  103.     }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement