TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

35.7% (5/14)

Submission's AC Ratio

11.5% (15/130)

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 1

6
0 0 0 7122 7122 8763

Sample Output 1

14

Sample Input 2

10
0 0 0 0 0 0 0 0 0 0

Sample Output 2

90

Hints

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

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

Problem Source

hansonyu123

Subtasks

No. Testdata Range Score
1 0~20 100

Testdata and Limits

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