Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader
- import java.io.InputStreamReader
- import scala.collection.mutable
- object test {
- def main(args: Array[String]) {
- val inputStreamReader = new InputStreamReader(System.in)
- val in1 = new BufferedReader(inputStreamReader)
- var n: Int = 0
- var k: Int = 0
- var str = in1.readLine().split(" ")
- n = str(0).toInt
- k = str(1).toInt
- var mas = new Array[(Long, Long)](n)
- for (i <- 0 until n) {
- str = in1.readLine().split(" ")
- mas(i) = (str(1).toInt, str(0).toInt)
- }
- def sorted(x: (Long, Long), y: (Long, Long)): Boolean = {
- x._1 > y._1
- }
- mas = mas.sortWith((x, y) => sorted(x, y))
- var heap = new Array[Long](n);
- var size: Int = 0
- var lengthOfKMax: Long = 0
- var answer: Long = 0
- def Push(value: Long): Boolean = {
- var index: Int = size
- size = size + 1
- heap(index) = value
- var par: Int = 0
- var tmp: Long = 0
- while (index > 0) {
- par = (index - 1) >> 1
- if (heap(index) > heap(par)) {
- tmp = heap(index)
- heap(index) = heap(par)
- heap(par) = tmp
- index = par
- } else {
- index = 0
- }
- }
- return true
- }
- def PollFirst(): Long = {
- var answer: Long = heap(0)
- var index: Int = 0
- var flag: Boolean = true
- size = size - 1
- heap(0) = heap(size)
- var nxt: Int = 0
- var tmp: Long = 0
- var left: Int = 0
- var right: Int = 0
- while (flag) {
- nxt = index
- left = (index << 1) + 1
- right = (index << 1) + 2
- if (left < size) {
- if (heap(left) > heap(index)) {
- nxt = left
- }
- }
- if (right < size) {
- if (heap(right) > heap(nxt)) {
- nxt = right
- }
- }
- if (nxt != index) {
- tmp = heap(nxt)
- heap(nxt) = heap(index)
- heap(index) = tmp
- index = nxt
- } else {
- flag = false
- }
- }
- return answer
- }
- for (i <- 0 until n) {
- if(i + 1 > k){
- lengthOfKMax += mas(i)._2
- Push(-mas(i)._2)
- lengthOfKMax += PollFirst()
- } else {
- lengthOfKMax += mas(i)._2
- Push(-mas(i)._2)
- }
- if (lengthOfKMax * mas(i)._1 > answer) {
- answer = lengthOfKMax * mas(i)._1
- }
- }
- println(answer)
- in1.close()
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement