As in the title, the problem is as follows:
Given a set ({$h_1, h_2...h_n$},{$p_1, p_2...p_n$},{$c_1, c_2...c_n$}, {$B$})
where: $ n ≤ 30000 $, $1≤c_k≤10000$, $0≤h_k≤1$, $0≤p_k≤1$, $1≤B≤100000$. \begin{array}{ll} \text{maximize} & (h_1i_1+h_2i_2...h_ni_n)*(p_1i_1+p_2i_2...p_ni_n)\\ \text{subject to}& c_1i_1+c_2i_2...c_ni_n \le B \\ \end{array}
I saw it in an ICPC practice set, and I been trying to figure what algorithm/method I need to solve it. It seems to be related to linear programming or convex optimization. I want learn more about the subject, so what I'm looking for the most the most its if someone can identify what type of problem this is and point me to some tutorial or lecture.
Note that input is very large. So the algorithm has to be $O(n)$ or $O(nlog(n))$ and that $i_k$ is a real number and $B, c_k$ are integers.
The problem can be summarized as $\max\{ x^TQx : a^Tx \leq b\}$, where $Q$ is not necessarily negative semidefinite. An optimization problem with a quadratic objective and just one linear constraint is easy, since it satisfies strong duality. That can be proven via the S-lemma.
For more information, see these lecture notes or Appendix B.1 of the (free) book Convex Optimization by Boyd and Vandenberghe.
upd As a computer scientist you may be interested in multi-objective swarm optimization (or variants thereof). Your objectives are maximizing $h_1i_1+h_2i_2...h_ni_n$ and $p_1i_1+p_2i_2...p_ni_n$. Among the Pareto optimal solutions, you multiply both quantities and select the solution with the highest outcome.