Partition - MarisaOJ: Marisa Online Judge

Given the sequence

$A$ with

$n$ elements

$a_1, a_2, ..., a_n$ . A subarray of

$A$ is defined as a sequence of consecutive elements in

$A$ . Divide the array into as many subarrays as possible such that the sum of elements in the preceding subarray is not less than the sum of elements in the succeeding subarray, and each element of array

$A$ belongs to exactly one subarray. ### Input - The first line contains a positive integer

$n (1 \le n \le 5 \times 10^5)$ . - The next line contains

$n$ elements of the array

$A = (a_1, a_2, ..., a_n)$ , where

$1 \le a_i \le 10^9$ . ### Output - Output a single integer, the number of subarrays that satisfy the given condition. ### Constraints - 20% of tests have

$n \le 20$ . - 30% of tests have

$n \le 1000$ . - The remaining 50% of tests have no additional constraints. ### Example Input:

$4 6 5 2 3$

Output:

$3$

Đề thi chọn đội dự tuyển chuyên ĐHSP, năm XXXX
	Digits
	Partition
	Green lines
	Treasure
	Shortest path
	Vaccination

Topic

Binary search

Greedy

Dynamic Programming

Rating

1900

Solution (0)

Solution