Загрузка данных


package main

import (
	"fmt"
	"sort"
	"container/heap"
)

type sortStruct struct {
	Index int
	Diff int
}

type Heap []*sortStruct

func (h Heap) Len() int {
	return len(h)
}

func (h Heap) Less(i, j int) bool {
	return h[i].Diff < h[j].Diff
}

func (h Heap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(*sortStruct))
}

func (h *Heap) Pop() any {
	elem := (*h)[len(*h) - 1]
	*h = (*h)[:len(*h) - 1]
	return elem
}

func main() {
	var a, b, n int
	fmt.Scanf("%d %d %d", &a, &b, &n)

	x := make([]int, n)
	y := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d %d", &x[i], &y[i])
	}

	sortedArr := make([]sortStruct, n)
	for i := 0; i < n; i++ {
		sortedArr[i] = sortStruct{
			Index: i,
			Diff: x[i] - y[i],
		}
	}

	sort.Slice(
		sortedArr,
		func(i, j int) bool {
			return sortedArr[i].Diff > sortedArr[j].Diff
		},
	)

	bestBackend := make([]int, n)
	bestML := make([]int, n)

	minHeap := &Heap{}
	heap.Init(minHeap)
	summa := 0
	for i := 0; i < a; i++ {
		minHeap.Push(
			&sortStruct{
				Index: sortedArr[i].Index,
				Diff: x[sortedArr[i].Index],
			},
		)
		summa += x[sortedArr[i].Index]
	}
	bestBackend[a - 1] = summa

	for i := a; i < n; i++ {
		minElem := minHeap.Pop().(*sortStruct)
		if minElem.Diff > x[sortedArr[i].Index] {
			minHeap.Push(minElem)
		} else {
			minHeap.Push(
				&sortStruct{
					Index: sortedArr[i].Index,
					Diff: x[sortedArr[i].Index],
				},
			)
			summa = summa - minElem.Diff + x[sortedArr[i].Index]
		}
		bestBackend[i] = summa
	}

	minHeap = &Heap{}
	heap.Init(minHeap)
	summa = 0
	for i := n - 1; i >= n - b; i-- {
		minHeap.Push(
			&sortStruct{
				Index: sortedArr[i].Index,
				Diff: y[sortedArr[i].Index],
			},
		)
		summa += y[sortedArr[i].Index]
	}
	bestML[n - b] = summa

	for i := n - b - 1; i >= 0; i-- {
		minElem := minHeap.Pop().(*sortStruct)
		if minElem.Diff > y[sortedArr[i].Index] {
			minHeap.Push(minElem)
		} else {
			minHeap.Push(
				&sortStruct{
					Index: sortedArr[i].Index,
					Diff: y[sortedArr[i].Index],
				},
			)
			summa = summa - minElem.Diff + y[sortedArr[i].Index]
		}
		bestML[i] = summa
	}

	res := 0
	if a == 0 {
		if b == 0 {
			res = 0
		} else {
			for border := 0; border <= n - b; border++ {
				if bestML[border] > res {
					res = bestML[border]
				}
			}
		}
	} else if b == 0 {
		for border := a - 1; border < n; border++ {
			if bestBackend[border] > res {
				res = bestBackend[border]
			}
		}
	} else {
		for border := a - 1; border < n - b; border++ {
			if bestBackend[border] + bestML[border + 1] > res {
				res = bestBackend[border] + bestML[border + 1]
			}
		}
	}

	fmt.Println(res)
}