Berry Picking

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
 
void fileIO(string filename) {
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
int MOD = 1;
 
bool cmp(int &a, int &b) {
	// Ordena por el máximo módulo, para que Bessie obtenga la máxima cantidad de sobras
	return (a % MOD) > (b % MOD);
}
 
void solve() {
	int N, K;
	cin >> N >> K;
	vector<int> A(N);
	int maxD = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		maxD = max(maxD, A[i]);
	}
	int mx = 0;
	for (int i = 1; i <= maxD; i++) {
		int amount = 0;
		// El bucle calcula cuántos grupos de "i" bayas se pueden poner en una
		// canasta
		for (int j = 0; j < N; j++) { amount += A[j] / i; }
		// Si la cantidad no alcanza para K / 2 canastas, no es válida
		if (amount < K / 2) { continue; }
		if (amount >= K) {
			// Si hay al menos "i" secciones para Bessie y
			// Ellie, entonces Bessie puede recolectar (K / 2) * i bayas
			mx = max(mx, (K / 2) * i);
			continue;
		}
		MOD = i;
		sort(all(A), cmp);
		// Damos la máxima cantidad de sobras a Bessie
		int cur = (amount - K / 2) * i;
		for (int j = 0; j < N && j + amount < K; j++) { cur += A[j] % i; }
		mx = max(mx, cur);
	}
	cout << mx << "\n";
}
 
int main() {
	fileIO("berries");
 
	solve();
}

import java.io.*;
import java.util.*;
 
public class Berries {
	static int N, K;
	static int[] B;
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader("berries.in");
		N = in.nextInt();
		K = in.nextInt();
		B = new int[N];
		int max = -1;
		for (int i = 0; i < N; i++) {
			B[i] = in.nextInt();
			max = Math.max(max, B[i]);
		}
 
		int res = -1;
		for (int i = 1; i <= max; i++) {
			int count = 0;
			int[] leftOver = new int[N];
			for (int j = 0; j < N; j++) {
				count += B[j] / i;
				leftOver[j] = B[j] % i;
			}
 
			if (count >= K) {
				// Si count alcanza tanto para Bessie como para Elsie, entonces
				// podemos asignar K/2 * i a Bessie
				res = Math.max(res, K / 2 * i);
			} else if (count >= K / 2) {
				// Si count solo alcanza para Elsie y parte de Bessie, entonces
				// podemos tomar de las sobras.
				int berries = 0;
				berries += (count - K / 2) * i;
				Arrays.sort(leftOver);
				int ix = leftOver.length - 1;
				for (int j = count - K / 2; j < K / 2; j++) {
					if (ix < 0) continue;
					berries += leftOver[ix--];
				}
 
				res = Math.max(res, berries);
			}
		}
 
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new FileWriter("berries.out")));
		out.println(res);
		out.close();
	}
 
	// BeginCodeSnip{Input Reader}
	private static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
 
		public InputReader() {
			try {
				reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			} catch (Exception e) {
				throw new NullPointerException("Could not create input stream");
			}
		}
 
		public InputReader(String fileName) {
			try {
				reader = new BufferedReader(new FileReader(new File(fileName)), 32768);
			} catch (Exception ex) {
				throw new NullPointerException(
				    "Input file does not exist! Put it in the project folder.");
			}
			tokenizer = null;
		}
 
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) { throw new RuntimeException(e); }
			}
			return tokenizer.nextToken();
		}
 
		public boolean hasNextInt() throws IOException { return reader.ready(); }
 
		public int nextInt() { return Integer.parseInt(next()); }
 
		public double nextDouble() { return Double.parseDouble(next()); }
 
		public long nextLong() { return Long.parseLong(next()); }
 
		public char nextChar() { return next().charAt(0); }
 
		/**
		 * When you call next(), that entire line will be skipped.
		 * No flushing buffers.
		 * Doesn't work when you want to scan the remaining line.
		 *
		 * @return entire line
		 */
 
		public String nextLine() {
			String str = "";
			try {
				str = reader.readLine();
				tokenizer = null;
			} catch (IOException e) { throw new RuntimeException(e); }
			return str;
		}
	}
	// EndCodeSnip
}

with open("berries.in") as read:
	n, k = map(int, read.readline().split())
	berries = [*map(int, read.readline().split())]
 
ans = 0
for i in range(1, max(berries) + 1):
	mod = i
	full = 0  # número de canastas llenas
	tmp = 0
 
	# suma de sobras
	for j in range(n):
		full += berries[j] // mod
 
	# si la cantidad no alcanza para k / 2 canastas, no es válida
	if full < k / 2:
		break
 
	"""
	si hay al menos k secciones para Bessie y Elsie,
	Bessie puede recibir (k / 2) * i bayas
	"""
	if full >= k:
		ans = max(ans, (k // 2) * i)
		continue
	idx = (full - k // 2) * i
 
	# ordenamos la lista de bayas por módulo para que Bessie obtenga la máxima cantidad de sobras
	berries.sort(key=lambda x: (x % mod), reverse=True)
 
	# calculamos la máxima cantidad de sobras que Bessie puede tomar
	while tmp < (k - full):
		if tmp < len(berries):
			idx += berries[tmp] % mod
			tmp += 1
		else:
			break
 
	ans = max(ans, idx)
 
print(ans, file=open("berries.out", "w"))

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("berries.in", "r", stdin);
 
	int N, K;
	cin >> N >> K;
	vector<int> B(N);
	for (int i = 0; i < N; i++) { cin >> B[i]; }
	int m = 0;
	for (int s = 1;; s++) {
		int full = 0;
		for (int n : B) { full += n / s; }
		full = min(full, K);
		if (full < K / 2) { break; }
		if (full < K) {
			nth_element(B.begin(), B.begin() + min(N, K - full) - 1, B.end(),
			            [&](int a, int b) { return a % s > b % s; });
		}
		int bessie = (full - K / 2) * s;
		for (int i = 0; i < min(N, K - full); i++) { bessie += B[i] % s; }
		m = max(m, bessie);
	}
 
	freopen("berries.out", "w", stdout);
	cout << m << endl;
}

import java.io.*;
import java.util.*;
 
public class Berries {
	static int s;
	static Random rand;
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new FileReader(new File("berries.in")));
		rand = new Random();
		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] B = new int[N];
		st = new StringTokenizer(r.readLine());
		for (int i = 0; i < N; i++) { B[i] = Integer.parseInt(st.nextToken()); }
		int m = 0;
		for (s = 1;; s++) {
			int full = 0;
			for (int n : B) { full += n / s; }
			full = Math.min(full, K);
			if (full < K / 2) { break; }
			if (full < K && K - full < N) { quickselect(B, K - full); }
			int bessie = (full - K / 2) * s;
			for (int i = 0; i < N && i < K - full; i++) { bessie += B[i] % s; }
			m = Math.max(m, bessie);
		}
 
		PrintWriter pw = new PrintWriter(new FileWriter("berries.out"));
		pw.println(m);
		pw.close();
	}
 
	// BeginCodeSnip{Quickselect Function}
	/**
	 * Rearranges A such that A[i] contains the
	 * ith greatest element in the list (mod s)
	 * and A[j] % s >= A[i] % s for all 0 <= j <= i.
	 */
	static void quickselect(int[] A, int i) {
		int l = 0, r = A.length - 1;
		while (l < r) {
			int j = partition(A, l, r);
			if (j == i) {
				return;
			} else if (j < i) {
				l = j + 1;
			} else {
				r = j - 1;
			}
		}
	}
 
	static int partition(int[] A, int l, int r) {
		int m = l;
		swap(A, l + rand.nextInt(r - l), r);
		for (int i = l; i < r; i++) {
			if (A[i] % s > A[r] % s) {
				swap(A, i, m);
				m++;
			}
		}
		swap(A, m, r);
		return m;
	}
 
	static void swap(int[] A, int i, int j) {
		int t = A[i];
		A[i] = A[j];
		A[j] = t;
	}
	// EndCodeSnip
}

import sys
import random
import itertools
 
 
def quickselect(A: list, i: int, key=lambda x: x):
	"""
	Rearranges A such that A[i] contains the ith smallest element in the list.
	It also makes it so that key(A[j]) <= key(A[i]) for all 0 <= j <= i.
	"""
 
	def partition():
		def swap(i, j):
			A[i], A[j] = A[j], A[i]
 
		m = l
		swap(random.randint(l, r - 1), r)
		for i in range(l, r):
			if key(A[i]) < key(A[r]):
				swap(i, m)
				m += 1
		swap(m, r)
		return m
 
	l, r = 0, len(A) - 1
	while l < r:
		j = partition()
		if j == i:
			return
		elif j < i:
			l = j + 1
		else:
			r = j - 1
 
 
with open("berries.in") as read:
	N, K = map(int, read.readline().split())
	B = list(map(int, read.readline().split()))
 
m = 0
for s in itertools.count(start=1):
	full = min(K, sum(b // s for b in B))
	if full < K // 2:
		break
	if full < K and K - full < N:
		quickselect(B, K - full, lambda x: -(x % s))
	bessie = (full - K // 2) * s + sum(x % s for x in B[: K - full])
	m = max(m, bessie)
 
print(m, file=open("berries.out", "w"))