calplus

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn An có một dãy số gồm \(N\) phần tử nguyên dương \(a_1,a_2,...,a_N\). An muốn tính tổng các số trong dãy. Vấn đề ở đây là chiếc máy tính của An khá chậm nên cậu ta muốn tìm cách tính tổng các số nguyên dương trong dãy sao cho thời gian máy tính hoạt động nhỏ nhất có thể. Biết rằng thời gian để tính tổng hai số nguyên dương \(x\) và \(y\) là \((x+y)^2\).

\(\textbf{Yêu cầu:}\) Bạn hãy đưa ra thời gian ít nhất để máy tính có thể tính được tổng cả dãy số mà An muốn tính.

Input

  • Dòng đầu tiên gồm số nguyên dương \(N\) \((N \le 3000)\).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^4)\).

Output

  • In ra một số duy nhất là kết quả bài toán.

Scoring

  • Subtask \(1\) (\(60\%\) số điểm): \(N \le 300\).
  • Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input 
3
3 4 5
Output 
193
Note
  • Tính \(3 + 4 = 7\) với thời gian \((3 + 4)^2 =49\);
  • Tính \(7 + 5 = 12\) với thời gian \((7 +5)^2=144\);
  • Như vậy tổng thời gian máy tính phải thực hiện là \(49+144=193\).

Bình luận