Mảng cộng dồn - Mảng tiền tố (Prefix sum) - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Tổng k số	100 (p)	0.5s	256M
2	Tổng dãy con	100 (p)	1.0s	256M
3	Dải số	100 (p)	1.0s	256M
4	Tích đặc biệt	200 (p)	1.0s	256M

1. Tổng k số

Điểm: 100 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,..,a_N\) và số nguyên dương \(K\). Chọn ra \(K\) phần tử liên tiếp sao cho tổng của chúng là lớn nhất. In ra giá trị đó

Input

Dòng 1: hai số nguyên dương \(N\) và \(K\) \((K \le N \le 10^5)\);
Dòng 2: gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

In ra đáp án thỏa mãn yêu cầu đề bài.

Example

Test 1

Input

6 2
2 4 5 2 9 1

Output

2. Tổng dãy con

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên gồm n phần tử \(a_1,a_2,\cdots,a_n\) \((|a_i| \leq 10^9)\). Cho giá trị \(x\) và \(q\) câu hỏi có dạng \(S(u,v)\). Với \(S(u,v)\) là tổng các giá trị của các phần tử từ \(u\) đến \(v\).

Yêu cầu: Đếm xem trong \(q\) câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn \(x\).

Input

Dòng đầu tiên chứa ba số nguyên dương \(n,x,q (x \leq 10^9,q \leq 10^5)\).
Dòng thứ hai chứa \(a_1,a_2,\cdots,a_n (|a_i| \leq 10^9)\).
\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u,v (1 \leq u \leq v \leq n)\).

Output

In ra một số nguyên là số lượng câu hỏi có giá trị nhỏ hơn \(x\)

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(n \leq 500\)
Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^4\)
Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^5\)

Example

Test 1

Input

Output

Note

\(S(2,3)=2+1=3<x=6\)
\(S(3,4)=1+6=7>x=6\)
\(S(5,5)=5<x=6\)
Vậy có 2 câu hỏi có giá trị nhỏ hơn \(x=6\)

3. Dải số

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một số nguyên dương \(n\) và một mảng \(A\) chứa \(n\) số nguyên (có thể âm). Bạn muốn cắt một nhát cắt trên mảng đó để chia mảng đó thành hai đoạn trái và phải, sao cho cả hai đoạn đều có ít nhất một phần tử và tổng các phần tử của hai đoạn bằng nhau.

Đề bài yêu cầu đếm có bao nhiêu cách cắt thỏa mãn điều kiện trên.

Input

Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 2*10^5)\)
Dòng thứ hai chứa \(n\) số nguyên \(A_i,\) là số thứ \(i\) của mảng \(A (|A_i| \leq 10^9)\)

Output

Số cách cắt mảng \(A\) cho trước, sao cho tổng của phân đoạn trái và phân đoạn phải sau khi cắt có tổng các phần tử bằng nhau.

Example

Test 1

Input

4
1 2 2 1

Output

Note

Có \(1\) cách cắt là \([1, 2]\) / \([2, 1]\)

Test 2

Input

6
1 1 1 3 -3 3

Output

Note

Có \(2\) cách cắt là:

\([1, 1, 1]\) / \([3, -3, 3]\)
\([1, 1, 1, 3, -3]\) / \([3]\)

4. Tích đặc biệt

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) phần tử số nguyên. Tìm tổng các tích của của mỗi phần tử \(A[i]\) với các phần tử \(A[j]\) với mọi \(j>i\).

Input

Dòng đầu ghi số \(N\) \((N \leq 10^6)\)
Dòng tiếp theo ghi \(N\) số nguyên, các số cách nhau bởi dấu cách \((|A[i]| \leq 10^6)\)

Output

Ghi một số là kết quả của bài toán

Example

Test 1

Input

4
9 3 4 2

Output

Note

Tích = \((9\cdot3 + 9\cdot4 + 9\cdot2) + (3\cdot4 + 3\cdot2) + (4\cdot2) = 107\)

Nguồn: CĐ DHBB '20