Handshake

Análisis oficial 

Explicación

Es más fácil resolver este problema considerando primero una solución cuadrática. Para resolverlo en $\mathcal{O}(N^2\log{N})$, podemos hallar todos los valores posibles de apretones de mano, ordenarlos y tomar los $M$ mayores.

Para optimizar esta solución, podemos usar búsqueda binaria. Hacemos búsqueda binaria sobre el valor $K$ tal que nuestros $M$ apretones de mano más grandes tienen valores $\geq K$ y los restantes tienen valores $\leq K$.

Para esto, ordenamos $A$ en orden no creciente y construimos un arreglo de sumas de prefijos, $\texttt{pref}$. Luego, para cada valor de $K$ que comprobamos con búsqueda binaria, usamos dos punteros para calcular el $\texttt{benefit}$ y el $\texttt{count}$ totales. Para cada índice $i$, hallamos el último índice $j$ tal que $A_i + A_j \geq K$. Al decrementar $i$ en $1$, nunca decrementamos $j$, lo que permite un recorrido en $\mathcal{O}(N)$.

Nuestra adición a $\texttt{count}$ se obtiene del hecho de que si $j$ es el último índice tal que $A_i + A_j \geq K$, podemos emparejar a la persona del índice $i$ con las primeras $j$ personas.

Nuestra adición a $\texttt{benefit}$ se obtiene del hecho de que cada uno de los $j$ apretones de mano, $(l, i)$, contribuye $A_l+A_i$ exactamente una vez para todo $l$ con $1 \leq l \leq j$. Esto da la fórmula $\texttt{benefit}=\texttt{benefit} +\sum_{l=1}^{j} (A_l+A_i)$, que es equivalente a $\texttt{benefit}=\texttt{benefit} +\sum_{l=1}^{j} A_l+A_i\cdot j$. Podemos usar sumas de prefijos para hallar $\sum_{l=1}^{j} A_l$ en $\mathcal{O}(1)$, lo que da nuestra fórmula.

Para el $K$ óptimo, el resultado es $\texttt{benefit}-K\cdot (\texttt{count}-M)$. Esto es porque, para el resultado óptimo, los apretones de mano con valor exactamente $K$ se pueden tomar o no. Cuando hallamos el $K$ óptimo, $\texttt{benefit}$ incluirá todos los apretones de mano de valor $K$. Para ajustar este sobreconteo, restamos $K\cdot (\texttt{count}-M)$, ya que no deberíamos tomar $\texttt{count}-M$ apretones de mano de valor exactamente $K$.

Implementación

Complejidad temporal: $\mathcal{O}(N\log{N})$

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int MAXV = 200000;
 
int main() {
	int n;
	ll m;
	cin >> n >> m;
 
	vector<int> a(n);
	vector<ll> pref(n + 1, 0);
 
	for (int &x : a) { std::cin >> x; }
 
	sort(a.rbegin(), a.rend());
	for (int i = 0; i < n; i++) { pref[i + 1] = a[i] + pref[i]; }
 
	int lo = 0, hi = MAXV;
	ll res = 0;
 
	while (lo <= hi) {
		ll count = 0, benefit = 0;
		int k = lo + (hi - lo) / 2;
 
		int j = 0;
		for (int i = n - 1; i >= 0; i--) {
			while (j < n && a[i] + a[j] >= k) { j++; }
			count += j;
			benefit += 1LL * j * a[i] + pref[j];
		}
		if (count >= m) {
			lo = k + 1;
			res = benefit - (count - m) * k;
		} else {
			hi = k - 1;
		}
	}
 
	cout << res << '\n';
	return 0;
}

import java.io.*;
import java.util.*;
 
public class Main {
 
	private static int MAXV = 200000;
 
	public static void main(String[] args) throws Exception {
 
		Kattio io = new Kattio();
		int n = io.nextInt();
		long m = io.nextLong();
 
		Integer[] a = new Integer[n];
		for (int i = 0; i < n; i++) { a[i] = io.nextInt(); }
		Arrays.sort(a, Collections.reverseOrder());
 
		long[] pref = new long[n + 1];
		for (int i = 0; i < n; i++) { pref[i + 1] = a[i] + pref[i]; }
 
		int lo = 0, hi = MAXV;
		long res = 0;
 
		while (lo <= hi) {
			long count = 0, benefit = 0;
			int k = lo + (hi - lo) / 2;
 
			int j = 0;
			for (int i = n - 1; i >= 0; i--) {
				while (j < n && a[i] + a[j] >= k) { j++; }
				count += j;
				benefit += (long)j * a[i] + pref[j];
			}
			if (count >= m) {
				lo = k + 1;
				res = benefit - (count - m) * k;
			} else {
				hi = k - 1;
			}
		}
 
		io.println(res);
		io.close();
	}
 
	// BeginCodeSnip{Kattio}
}