Maximum Performance of a Team

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        const int MOD = 1'000'000'007;
        vector<pair<int,int>> w(n);
        for (int i = 0; i < n; ++i) w[i] = {efficiency[i], speed[i]};
        sort(w.begin(), w.end(), greater<>());
        priority_queue<int, vector<int>, greater<int>> pq;
        long long sumSpeed = 0, best = 0;
        for (auto& [e, s] : w) {
            sumSpeed += s;
            pq.push(s);
            if ((int)pq.size() > k) { sumSpeed -= pq.top(); pq.pop(); }
            best = max(best, sumSpeed * e);
        }
        return best % MOD;
    }
};

import (
    "container/heap"
    "sort"
)

type minHeap []int

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func maxPerformance(n int, speed []int, efficiency []int, k int) int {
    const MOD = 1_000_000_007
    type pair struct{ e, s int }
    w := make([]pair, n)
    for i := 0; i < n; i++ {
        w[i] = pair{efficiency[i], speed[i]}
    }
    sort.Slice(w, func(i, j int) bool { return w[i].e > w[j].e })
    pq := &minHeap{}
    var sumSpeed, best int64
    for _, p := range w {
        sumSpeed += int64(p.s)
        heap.Push(pq, p.s)
        if pq.Len() > k {
            sumSpeed -= int64(heap.Pop(pq).(int))
        }
        cur := sumSpeed * int64(p.e)
        if cur > best {
            best = cur
        }
    }
    return int(best % MOD)
}

import heapq
from typing import List

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        MOD = 10**9 + 7
        engineers = sorted(zip(efficiency, speed), reverse=True)
        pq: List[int] = []
        sum_speed = 0
        best = 0
        for e, s in engineers:
            sum_speed += s
            heapq.heappush(pq, s)
            if len(pq) > k:
                sum_speed -= heapq.heappop(pq)
            best = max(best, sum_speed * e)
        return best % MOD

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l] < this.h[s]) s = l;
                if (r < n && this.h[r] < this.h[s]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function maxPerformance(n, speed, efficiency, k) {
    const MOD = 1000000007n;
    const w = [];
    for (let i = 0; i < n; i++) w.push([efficiency[i], speed[i]]);
    w.sort((a, b) => b[0] - a[0]);
    const pq = new MinHeap();
    let sumSpeed = 0n;
    let best = 0n;
    for (const [e, s] of w) {
        sumSpeed += BigInt(s);
        pq.push(s);
        if (pq.size() > k) sumSpeed -= BigInt(pq.pop());
        const cur = sumSpeed * BigInt(e);
        if (cur > best) best = cur;
    }
    return Number(best % MOD);
}

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        final int MOD = 1_000_000_007;
        int[][] w = new int[n][2];
        for (int i = 0; i < n; i++) {
            w[i][0] = efficiency[i];
            w[i][1] = speed[i];
        }
        Arrays.sort(w, (a, b) -> b[0] - a[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long sumSpeed = 0, best = 0;
        for (int[] p : w) {
            sumSpeed += p[1];
            pq.offer(p[1]);
            if (pq.size() > k) sumSpeed -= pq.poll();
            best = Math.max(best, sumSpeed * p[0]);
        }
        return (int)(best % MOD);
    }
}

class MinHeap {
    private h: number[] = [];
    size(): number { return this.h.length; }
    peek(): number { return this.h[0]; }
    push(v: number): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop() as number;
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l] < this.h[s]) s = l;
                if (r < n && this.h[r] < this.h[s]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function maxPerformance(n: number, speed: number[], efficiency: number[], k: number): number {
    const MOD = 1000000007n;
    const w: [number, number][] = [];
    for (let i = 0; i < n; i++) w.push([efficiency[i], speed[i]]);
    w.sort((a, b) => b[0] - a[0]);
    const pq = new MinHeap();
    let sumSpeed = 0n;
    let best = 0n;
    for (const [e, s] of w) {
        sumSpeed += BigInt(s);
        pq.push(s);
        if (pq.size() > k) sumSpeed -= BigInt(pq.pop());
        const cur = sumSpeed * BigInt(e);
        if (cur > best) best = cur;
    }
    return Number(best % MOD);
}