TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

25.0% (3/12)

Submission's AC Ratio

17.9% (25/140)

Tags

Description

在許多年以前,那個硬體還沒有現在那麼先進的時代,有一群物理學家正在研究一個分子的性質。他們發現這個分子有$N=10^ 8$種狀態,分別標號為$0, 1, \ldots, N-1$。除此之外 ,他們發現不同狀態的分子之間不會有任何特別事的發生,但處在同一種狀態的分子會互相排斥,使得整個系統的能量增加。更具體地來說,如果處在狀態$i$的分子有$a_i$個,那麼系統總能量就是$\sum_{i=0}^ {N-1}a_i^ 2$。

現在這群物理學家正在研究$n\leq 10^ 6$個這樣的分子。他們有一個很大的資料庫記錄了所有分子的狀態,而他們現在想要估算系統總能量。然而當時的運算器太弱了,沒有足夠的空間可以算出所有的$a_i$。不過沒關係,畢竟他們是物理學家,答案不用那麼精準 :p 所以他們能容忍一些不太大的相對誤差。更具體地,他們希望得出來的答案跟正確的答案的相對誤差不要超過一成。

Input Format

第一行有一個正整數$n\leq 10^ 6$代表分子的個數。第二行包含$n$個非負整數$x_0,\ldots,x_{n-1}$, 代表$n$個分子的狀態。

Output Format

請輸出一個非負整數$E'$, 代表你估算出的系統總能量。
如果正確答案是$E$而且$0.9E\leq E'\leq 1.1E$,那麼你的答案將會被視為正確。

Sample Input

Sample Input 1:
6
0 0 0 7122 7122 8763

Sample Input 2:
10
0 0 0 0 0 0 0 0 0 0

Sample Output

Sample Output 1:
14

Sample Output 2:
90

Hints

Sample Output 2中的正確答案是100. 因為90跟100的相對誤差只有一成所以也會被視為正確。

註:本題的記憶體限制非常緊。請避免使用如iostream和math等等的引入檔減少記憶體浪費。

Problem Source

hansonyu123

Subtasks

For Testdata: 0 ~ 20, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5500 4260 1
1 5500 4260 1
2 5500 4260 1
3 5500 4260 1
4 5500 4260 1
5 5500 4260 1
6 5500 4260 1
7 5500 4260 1
8 5500 4260 1
9 5500 4260 1
10 5500 4260 1
11 5500 4260 1
12 5500 4260 1
13 5500 4260 1
14 5500 4260 1
15 5500 4260 1
16 5500 4260 1
17 5500 4260 1
18 5500 4260 1
19 5500 4260 1
20 5500 4260 1