Sum of products with bounded coefficients
An $O(n^2 \log r)$ bound can be obtained by Bézout's lemma:


  Lemma. For every integers $0 &lt; c_i \leq n$, $\gcd(c_1,\ldots,c_r) = \sum_i m_i c_i$ for some integers $m_i$ with $|m_i| \leq n \log r$.


This lemma is obtained by recursively applying Bézout's lemma on two variables and the identity $\gcd(x_1,x_2,x_3) = \gcd(\gcd(x_1,x_2),x_3)$.

Without loss of generality assume that $\gcd(c_1,\ldots,c_r) = 1$ by dividing $\gcd(c_1,\ldots,c_r)$ on both sides of $\sum_i m_i c_i = k$. By Bézout's lemma there exists integers $m_i$ with $|m_i| \leq n \log r$ such that 

$$k \cdot \sum_i m_i c_i = \sum_i (k \cdot m_i) c_i = k \cdot 1 \text,$$

by observing $k = O(n)$ we have the desired $m'_i = k \cdot m_i$ with $|m'_i| = O(n^2 \log r)$.



If you are searching for literature, the keyword is inhomogeneous linear Diophantine  equations, that is the equation $\sum_i m_i c_i = k$ when $k = 0$. For the homogeneous one, one can obtain a linear bound on $|m_i'|$, see e.g. this or this paper. As for the inhomogeneous one, I have not yet found such a result; however this paper seems relevant.