Advertisement
999ms

Untitled

Oct 1st, 2019
482
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 2.50 KB | None | 0 0
  1. import java.io.BufferedReader
  2. import java.io.InputStreamReader
  3. import scala.collection.mutable
  4.  
  5. object test {
  6.   def main(args: Array[String]) {
  7.     val inputStreamReader = new InputStreamReader(System.in)
  8.     val in1 = new BufferedReader(inputStreamReader)
  9.     var n: Int = 0
  10.     var k: Int = 0
  11.     var str = in1.readLine().split(" ")
  12.     n = str(0).toInt
  13.     k = str(1).toInt
  14.  
  15.     var mas = new Array[(Long, Long)](n)
  16.     for (i <- 0 until n) {
  17.       str = in1.readLine().split(" ")
  18.       mas(i) = (str(1).toInt, str(0).toInt)
  19.     }
  20.  
  21.     def sorted(x: (Long, Long), y: (Long, Long)): Boolean = {
  22.       x._1 > y._1
  23.     }
  24.  
  25.     mas = mas.sortWith((x, y) => sorted(x, y))
  26.  
  27.     var heap = new Array[Long](n);
  28.     var size: Int = 0
  29.    
  30.     var lengthOfKMax: Long = 0
  31.     var answer: Long = 0
  32.    
  33.     def Push(value: Long): Boolean = {
  34.       var index: Int = size
  35.       size = size + 1
  36.       heap(index) = value
  37.       var par: Int = 0
  38.       var tmp: Long = 0
  39.       while (index > 0) {
  40.         par = (index - 1) >> 1
  41.         if (heap(index) > heap(par)) {
  42.           tmp = heap(index)
  43.           heap(index) = heap(par)
  44.           heap(par) = tmp
  45.           index = par
  46.         } else {
  47.           index = 0
  48.         }
  49.       }
  50.       return true
  51.     }
  52.    
  53.     def PollFirst(): Long = {
  54.       var answer: Long = heap(0)
  55.       var index: Int = 0
  56.       var flag: Boolean = true
  57.       size = size - 1
  58.       heap(0) = heap(size)
  59.       var nxt: Int = 0
  60.       var tmp: Long = 0
  61.       var left: Int = 0
  62.       var right: Int = 0
  63.       while (flag) {
  64.         nxt = index
  65.         left = (index << 1) + 1
  66.         right = (index << 1) + 2
  67.         if (left < size) {
  68.           if (heap(left) > heap(index)) {
  69.             nxt = left
  70.           }
  71.         }
  72.         if (right < size) {
  73.           if (heap(right) > heap(nxt)) {
  74.             nxt = right
  75.           }
  76.         }
  77.         if (nxt != index) {
  78.           tmp = heap(nxt)
  79.           heap(nxt) = heap(index)
  80.           heap(index) = tmp
  81.           index = nxt
  82.         } else {
  83.           flag = false
  84.         }
  85.       }
  86.       return answer
  87.     }
  88.  
  89.     for (i <- 0 until n) {
  90.       if(i + 1 > k){
  91.         lengthOfKMax += mas(i)._2
  92.         Push(-mas(i)._2)
  93.         lengthOfKMax += PollFirst()
  94.       } else {
  95.         lengthOfKMax += mas(i)._2
  96.         Push(-mas(i)._2)
  97.       }
  98.       if (lengthOfKMax * mas(i)._1 > answer) {
  99.         answer = lengthOfKMax * mas(i)._1
  100.       }
  101.     }
  102.    
  103.     println(answer)
  104.    
  105.     in1.close()
  106.   }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement