AtCoder Beginner Contest 376 E

https://atcoder.jp/contests/abc376/tasks/abc376_e

max Aを決めて、その条件でBの和が最小になるようにすると考えるとわかりやすいです。

// Max × Sum
#![allow(non_snake_case)]

use std::collections::BinaryHeap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Case ////////////////////

struct Case {
    K: usize,
    AB: Vec<(i64, i64)>
}

impl Case {
    fn max(&self) -> i64 {
        let mut s = self.AB[..self.K].iter().map(|&(_, b)| b).sum::<i64>();
        // max Aが最も小さいとき
        let mut min_mul: i64 = s * self.AB[self.K-1].0;
        let mut tree = BinaryHeap::new();
        for &(_, b) in self.AB[..self.K].iter() {
            tree.push(b)
        }
        for i in self.K..self.AB.len() {
            // max Aを決めたら、Sの中の最大のBを捨てて、max Aと対のBを加える
            let max_b = tree.pop().unwrap();
            tree.push(self.AB[i].1);
            s = s - max_b + self.AB[i].1;   // treeの和
            let mul = s * self.AB[i].0;
            if mul < min_mul {
                min_mul = mul
            }
        }
        min_mul
    }
    
    fn read() -> Case {
        let v: Vec<usize> = read_vec();
        let K = v[1];
        let A: Vec<i64> = read_vec();
        let B: Vec<i64> = read_vec();
        let mut AB: Vec<(i64, i64)> = A.into_iter().
                                        zip(B.into_iter()).collect();
        AB.sort_by_key(|&(a, _)| a);
        Case { K, AB }
    }
}


//////////////////// process ////////////////////

fn F(T: usize) {
    for _ in 0..T {
        let case = Case::read();
        println!("{}", case.max())
    }
}

fn main() {
    let T: usize = read();
    F(T)
}