Số điểm cao nhất

View as PDF




Time limit:
Pypy 3 5.0s
Python 3 5.0s
Memory limit:
C++11 10M
Pascal 10M
Pypy 3 1G
Python 3 1G

Author:
Problem types
Points: 200 (p) Time limit: 2.0s Memory limit: 256M Input: stdin Output: stdout

DeMen100ms là 1 con người đang ở tận cùng của sự cô đơn. Và cậu luôn ghét nhìn thấy người khác đi chơi với nhau. Một hôm, leanhduy123 rủ cậu đi ngồi cafe vỉa hè. Vì thấy mọi người ngoài đường đi chơi cùng nhau nên DeMen100ms rất cay cú.

  • Ở ngoài đường đang có \(N\) người được đánh số từ \(1\) đến \(N\).
  • Người thứ i có điểm hạnh phúc là \(HP[i]\).
  • Tổng số điểm hạnh phúc là : tổng của các tích \(HP[i] * HP[j]\) \((1 \leq i < j \leq n)\)

Yêu cầu: In ra tổng số điểm hạnh phúc có thể đạt được từ \(N\) người đó.

Input

  • Dòng đầu nhập \(N\) là người trên đường.
  • Dòng thứ 2 là \(N\) số điểm hạnh phúc của \(N\) người.

Output

  • In ra tổng điểm hạnh phúc của \(N\) người đó, vì kết quả có thể rất lớn nên lấy kết quả modulo cho \(10^9 + 7\)

Constraints

  • \(N \leq 5*10^6\)
  • \(0 < HP[i] \leq 3*10^4\)

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N \leq 5*10^3\).
  • Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
3
1 2 3 
Output
11
Note

Tổng hạnh phúc được tính như sau: \(HP[1]*HP[2] + HP[1]*HP[3] + HP[2]*HP[3]\).


Comments


  • 0
    mcsmuscle    1:46 p.m. 16 jan, 2022

    tăng mem của python lên đi ạ, e thấy làm kiểu gì cũng bị mem limit