Using an SVD $A=USV^T$, and setting $y=U^Tx$, $c=U^Tb$, you can reduce the problem to a diagonal one $$\min_{y\in\mathbb{R}^n} c^Ty + \frac12 y^T S^2 y = \min_{y\in\mathbb{R}^n} \sum_{i=1}^n c_i y_i + \frac12 \sigma_i^2 y_i^2,$$ which should be trivial because the variables are separated. The whole algorithm costs $O(nm^2)$, assuming you are careful in representing $U$ as a product of rotations (which is not completely trivial to do in Matlab/Python/whatever you are using: in Matlab, you'd have to start with a QR factorization of $A$ [C,R] = qr(A,c), for instance, and then do an SVD of $R$; in Python, I am afraid you need numpy.linalg.qr with option raw).

Using an SVD $A=USV^T$, and setting $y=U^Tx$, $c=U^Tb$, you can reduce the problem to a diagonal one $$\min_{y\in\mathbb{R}^n} c^Ty + \frac12 y^T S^2 y = \min_{y\in\mathbb{R}^n} \sum_{i=1}^n c_i y_i + \frac12 \sigma_i^2 y_i^2,$$ which should be trivial because the variables are separated. The whole algorithm costs $O(nm^2)$, assuming you are careful in representing $U$ as a product of rotations (which is not completely trivial to do in Matlab/Python/whatever you are using: in Matlab, you'd have to start with a QR factorization of $A$ [c,R] = qr(A,b), for instance, and then do an SVD of $R$; in Python, I am afraid you need numpy.linalg.qr with option raw). Or you can get $O(n^2m)$ if you just ignore the issue and use library SVD which returns a full matrix $U$.

Using an SVD $A=USV^T$, and setting $y=U^Tx$, $c=U^Tb$, you can reduce the problem to a diagonal one $$\min_{y\in\mathbb{R}^n} c^Ty + \frac12 y^T S^2 y = \min_{y\in\mathbb{R}^n} \sum_{i=1}^n c_i y_i + \frac12 \sigma_i^2 y_i^2,$$ which should be trivial because the variables are separated. The whole algorithm costs $O(nm^2)$.

Using an SVD $A=USV^T$, and setting $y=U^Tx$, $c=U^Tb$, you can reduce the problem to a diagonal one $$\min_{y\in\mathbb{R}^n} c^Ty + \frac12 y^T S^2 y = \min_{y\in\mathbb{R}^n} \sum_{i=1}^n c_i y_i + \frac12 \sigma_i^2 y_i^2,$$ which should be trivial because the variables are separated. The whole algorithm costs $O(nm^2)$, assuming you are careful in representing $U$ as a product of rotations (which is not completely trivial to do in Matlab/Python/whatever you are using: in Matlab, you'd have to start with a QR factorization of $A$ [C,R] = qr(A,c), for instance, and then do an SVD of $R$; in Python, I am afraid you need numpy.linalg.qr with option raw).