E - Square Price
Source: atcoder
Difficulty: 475

Problem Statement
There are
N
types of products, each having
10^{100}
units in stock.
You can buy any non-negative number of units of each product. To buy
k
units of the
i
-th product, it costs
k^2 P_i
yen.
If your total purchase cost is at most
M
yen, what is the maximum number of units you can buy in total?
Constraints
1 \leq N \leq 2 \times 10^{5}
1 \leq M \leq 10^{18}
1 \leq P_i \leq 2 \times 10^{9}
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
P_1
\ldots
P_N
Output
Print the answer.
Sample Input 1
3 9
4 1 9
Sample Output 1
3
If you buy one unit of the 1st product and two units of the 2nd product, the total purchase cost is
1^2 \times 4 + 2^2 \times 1 = 8
. It is impossible to buy four or more units in total with a total cost of at most
9
yen, so the answer is
3
.
Sample Input 2
10 1000
2 15 6 5 12 1 7 9 17 2
Sample Output 2
53

C++ solution:
#include <bits/stdc++.h>

using namespace std;
using i128 = __int128_t;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m;
    cin >> n >> m;

    vector<long long> P(n);
    for (int i = 0; i < n; i++)
    {
        cin >> P[i];
    }

    auto check = [&](long long mid) -> pair<i128, i128>
    {
        i128 cost = 0, cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (mid < P[i])
            {
                continue;
            }

            long long upper = mid / P[i];
            long long k = (upper + 1) / 2;

            cnt += k;
            cost += i128(P[i]) * k * k;

            if (cost > m)
            {
                break;
            }
        }

        return {cost, cnt};
    };

    long long l = 0, r = m + 1;
    while (r - l > 1)
    {
        long long mid = l + (r - l) / 2;
        (check(mid).first <= m ? l : r) = mid;
    }
    {
        auto [cost, cnt] = check(l);
        long long ans = cnt + (m - cost) / r;
        cout << fixed << setprecision(15);
        cout << ans << endl;
    }

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
)

func main() { solveE(os.Stdin, os.Stdout) }

func solveF(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	const M int = 5e5 + 5
	a := make([]int, M+1)
	for i := 0; i <= M; i++ {
		a[i] = i
	}
	tree := newLazySegmentTree(a)

	n := readNum(in)
	for i := 0; i < n; i++ {
		l, r := readTwoNums(in)
		idx1 := tree.lowerBound(1, 1, M, l)
		idx2 := tree.lowerBound(1, 1, M, r+1) - 1
		tree.update(1, idx1, idx2, 1)
	}

	q := readNum(in)
	for ; q > 0; q-- {
		x := readNum(in)
		fmt.Fprintln(out, tree.query(1, x, x))
	}
}

func solveE(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	n, m := readTwoNums(in)
	prices := readNNums(in, n)

	check := func(mxp int) (bool, int) {
		cnt, sum := 0, 0
		for i := 0; i < n; i++ {
			k := (mxp + prices[i]) / 2 / prices[i]
			cnt += k
			if k > int(2e9) || k*k > m/prices[i] || sum+k*k*prices[i] > m {
				return true, 0
			}
			sum += k * k * prices[i]
		}
		return false, cnt + (m-sum)/(mxp+1)
	}
	mxp := sort.Search(int(1e15), func(x int) bool { ok, _ := check(x); return ok })
	_, cnt := check(mxp - 1)
	// mxp 可能出现买不完的情况
	fmt.Fprintln(out, cnt)
}

func solveD(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	R, ans := readNum(in), 0
	for i := 0; i < R; i++ {
		v := sort.Search(R+1, func(j int) bool { return (2*j+1)*(2*j+1) > 4*R*R-(2*i+1)*(2*i+1) })
		// fmt.Fprintln(out, v)
		ans += v*2 - 1
		if i != 0 {
			ans += v*2 - 1
		}
	}
	fmt.Fprintln(out, ans)
}

func solveC(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	var q, op, x int
	a := []int{}
	rem, pre := 0, 0
	for fmt.Fscan(in, &q); q > 0; q-- {
		fmt.Fscan(in, &op)
		if op == 1 {
			fmt.Fscan(in, &x)
			a = append(a, pre)
			pre += x
		} else if op == 2 {
			rem++
		} else {
			fmt.Fscan(in, &x)
			fmt.Fprintln(out, a[x-1+rem]-a[rem])
		}
	}
}

func solveB(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	x := readNum(in)
	for n, fact := 1, 1; fact <= x; n++ {
		fact *= n
		if fact == x {
			fmt.Fprintln(out, n)
			return
		}
	}
}

func solveA(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	s := readString(in)
	fmt.Fprintln(out, (s[0]-'0')*(s[2]-'0'))
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

// 延迟标记
const todoInit = 0

type lazySeg []struct {
	l, r      int
	max, todo int
}

func (t lazySeg) do(o int, add int) {
	to := &t[o]
	to.max += add
	to.todo += add
}

func (lazySeg) mergeInfo(a, b int) int {
	return max(a, b)
}

func (t lazySeg) maintain(o int) {
	lo, ro := &t[o<<1], &t[o<<1|1]
	t[o].max = t.mergeInfo(lo.max, ro.max)
}

func (t lazySeg) build(a []int, o, l, r int) {
	t[o].l, t[o].r = l, r
	t[o].todo = todoInit
	if l == r {
		t[o].max = a[l]
		return
	}
	m := (l + r) >> 1
	t.build(a, o<<1, l, m)
	t.build(a, o<<1|1, m+1, r)
	t.maintain(o)
}

func (t lazySeg) spread(o int) {
	if add := t[o].todo; add != todoInit {
		t.do(o<<1, add)
		t.do(o<<1|1, add)
		t[o].todo = todoInit
	}
}

// 如果维护的数据（或者判断条件）具有单调性，我们就可以在线段树上二分
// 下面代码返回 [l,r] 内第一个值不低于 val 的下标（未找到时返回 n+1）
// o=1  [l,r] 1<=l<=r<=n
// https://codeforces.com/problemset/problem/1179/C
func (t lazySeg) lowerBound(o, l, r int, val int) int {
	if t[o].l == t[o].r {
		if t[o].max >= val {
			return t[o].l
		}
		return t[o].l + 1
	}
	t.spread(o)
	// 注意判断比较的对象是当前节点还是子节点，是先递归左子树还是右子树
	if t[o<<1].max >= val {
		return t.lowerBound(o<<1, l, r, val)
	}
	return t.lowerBound(o<<1|1, l, r, val)
}

// o=1  [l,r] 1<=l<=r<=n
func (t lazySeg) update(o, l, r int, add int) {
	if l <= t[o].l && t[o].r <= r {
		t.do(o, add)
		return
	}
	t.spread(o)
	m := (t[o].l + t[o].r) >> 1
	if l <= m {
		t.update(o<<1, l, r, add)
	}
	if m < r {
		t.update(o<<1|1, l, r, add)
	}
	t.maintain(o)
}

// o=1  [l,r] 1<=l<=r<=n
func (t lazySeg) query(o, l, r int) int {
	if l <= t[o].l && t[o].r <= r {
		return t[o].max
	}
	t.spread(o)
	m := (t[o].l + t[o].r) >> 1
	if r <= m {
		return t.query(o<<1, l, r)
	}
	if m < l {
		return t.query(o<<1|1, l, r)
	}
	vl := t.query(o<<1, l, r)
	vr := t.query(o<<1|1, l, r)
	return t.mergeInfo(vl, vr)
}

// a 从 0 开始
func newLazySegmentTree(a []int) lazySeg {
	t := make(lazySeg, 4*len(a))
	t.build(a, 1, 1, len(a)-1)
	return t
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.*;

class Solver {
  private final int n;
  private final long m;
  private final long[] ps;

  private long calculateCount(long price) {
    long mRest = m;
    double mRestD = 5 * m;
    long count = 0;
    for (long p : ps) {
      long x = price / p;
      long k = (x + 1) / 2;
      count += k;
      double kd = k;
      double pd = p;
      mRestD -= kd * kd * pd;
      mRest -= k * k * p;
      if (mRest < 0 || mRestD < 0.0) {
        return -1;
      }
    }
    return count + mRest / (price + 1);
  }

  public Solver(int n, long m, long[] ps) {
    this.n = n;
    this.m = m;
    this.ps = ps;
  }

  public long solve() {
    long ngPrice = 2_000_000_000_000_000_000L;
    long okPrice = -1;
    while (ngPrice - okPrice >= 2) {
      long price = (ngPrice + okPrice) / 2;
      long result = calculateCount(price);
      if (result < 0) {
        ngPrice = price;
      } else {
        okPrice = price;
      }
    }
    return calculateCount(okPrice);
  }
};


public class Main {
  private static void execute(ContestReader reader, ContestWriter out) {
    int n = reader.nextInt();
    long m = reader.nextLong();
    long[] ps = reader.nextLong(n);
    out.println(new Solver(n, m, ps).solve());
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    ContestWriter out = new ContestWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestWriter extends PrintWriter {
  ContestWriter(PrintStream printStream) {
    super(printStream);
  }

  public void printYN(boolean b) {
    println(b ? "Yes" : "No");
  }

  public void printYNList(List<Boolean> bList) {
    for (boolean b : bList) {
      printYN(b);
    }
  }

  public void printList(List<? extends Object> list) {
    for (Object object : list) {
      println(object);
    }
  }

  public void printListOneLine(List<? extends Object> list) {
    List<String> stringList = new ArrayList<>();
    for (Object object : list) {
      stringList.add(object.toString());
    }
    println(String.join(" ", stringList));
  }
}

class ContestReader {
  private static final int BUFFER_SIZE = 1024;
  
  private final InputStream stream;
  private final byte[] buffer;
  private int pointer;
  private int bufferLength;
  
  ContestReader(InputStream stream) {
    this.stream = stream;
    this.buffer = new byte[BUFFER_SIZE];
    this.pointer = 0;
    this.bufferLength = 0;
  }
  
  private boolean hasNextByte() {
    if (pointer < bufferLength) {
      return true;
    }
    
    pointer = 0;
    try {
      bufferLength = stream.read(buffer);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
    return bufferLength > 0;
  }
  
  private int readByte() {
    if (hasNextByte()) {
      return buffer[pointer++];
    } else {
      return -1;
    }
  }
  
  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }
  
  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[pointer])) {
      pointer++;
    }
    return hasNextByte();
  }
  
  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b)) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public String nextLine() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b) && b != 0x20) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public char nextChar() {
    return next().charAt(0);
  }
  
  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    int n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    long n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public String[] nextLine(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLine();
    }
    return array;
  }
  
  public char[] nextChar(int n) {
    char[] array = new char[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextChar();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public String[][] next(int n, int m) {
    String[][] matrix = new String[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = next();
      }
    }
    return matrix;
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public char[][] nextChar(int n, int m) {
    char[][] matrix = new char[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextChar();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}

class Pair<T extends Comparable<T>, U extends Comparable<U>> implements Comparable<Pair<T, U>> {
  T first;
  U second;

  Pair(T first, U second) {
    this.first = first;
    this.second = second;
  }

  public int compareTo(Pair<T, U> p) {
    int tResult = first.compareTo(p.first);
    if (tResult != 0) {
      return tResult;
    }
    return second.compareTo(p.second);
  }
}

class MyAssert {
  public static void myAssert(boolean flag, String message) {
    if (!flag) {
      throw new RuntimeException(message);
    }
  }
 
  public static void myAssert(boolean flag) {
    myAssert(flag, "");
  }
}

JavaScript solution:
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map((x, i) => (i == 0 ? Number(x) : BigInt(x)));
  const P = input[1].split(" ").map(Number);
  let ans = 0;

  const isOK = (mid) => {
    let cur = 0n;
    const cnt = Array(N).fill(0);
    for (let i = 0; i < N; i++) {
      cnt[i] = Math.floor(((mid / P[i]) + 1) / 2);
      cur += BigInt(cnt[i] ** 2) * BigInt(P[i]);
      if (cur > M) return false;
    }

    let res = cnt.reduce((acc, cur) => acc + cur, 0);
    for (let i = 0; i < N; i++) {
      let nex = BigInt(2 * cnt[i] + 1) * BigInt(P[i]);
      if (nex == BigInt(mid + 1)) {
        if (cur + nex > M) break;
        cur += nex;
        res++;
      }
    }
    ans = Math.max(ans, res);
    return true;
  };
  const lower_bound = () => {
    let ok = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    let ng = 10 ** 14; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    while (ng - ok > 1) {
      let mid = Math.floor((ok + ng) / 2);
      if (isOK(mid)) ok = mid;
      else ng = mid;
    }
    return ok;
  };

  lower_bound();
  console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));

Python solution:
N, M = map(int, input().split())

P = list(map(int, input().split()))

def f(x):
  cost = 0
  s = 0
  for p in P:
    k = (x//p + 1)//2
    cost += k**2 * p
    s += k
    if cost > M:
      return s, cost
  return s, cost

right = M
left = 0
rest = M
ans = 0
count = 0

while left <= right:
  mid = (right + left) // 2
  S, C = f(mid)
  
  if C <= M:
    ans = mid
    rest = M - C
    count = S
    left = mid +1
  else:
    right = mid -1
    
index = 0
while index < N and rest > ans:
  p= P[index]
  if (ans+1)%p == 0 and ((ans+1)//p) % 2 == 1:
    rest -= ans+1
    count += 1
  index += 1
print(count)

Ruby solution:
N,M,*P = $<.read.split.map(&:to_i)

B = ((1..M).bsearch{|b|
	m = 0
	P.any?{|p|
		k = (b/p+1)/2
		M<m += k*k*p
	}
}||1)-1
#p [:B,B]
K = P.map{|p| (B/p+1)/2 }
#p K

m = P.zip(K).sum{|p,k| k*k*p }
P.zip(K).map.with_index{|(p,k),i| [(k+k+1)*p,i] }.sort_by{|kkp,|kkp}.each{|kkp,i|
	if m+kkp<=M
		m += kkp
		K[i] += 1
	end
}
#p K
p K.sum