ISL 2013 C4

Let $n$ be a positive integer, and let $A$ be a subset of $\{1, \ldots, n\}$. An $A$-partition of $n$ into $k$ parts is a representation of $n$ as a sum $n=a_{1}+\cdots+a_{k}$, where the parts $a_{1}, \ldots, a_{k}$ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}$. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6 n}$ different parts. (Germany)