#PQJ1546x123. QOJ 1546_123

    ID: 2642 传统题 5000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训二分答案前缀和

QOJ 1546_123

The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 4 – Candies Candies There are N candies in a row on the table. Each candy has a value called deliciousness. The deliciousness of the candy which is located i-th from the left is Ai (1 ≤i ≤N). JOI-chan decided to eat some of these N candies. JOI-chan wants to maximize the sum of deliciousness of candies which she is going to eat. However, JOI-chan thinks that just choosing candies greedily is not interesting, so she makes a rule that she cannot choose two consecutive candies simultaneously. JOI-chan has not decided how many candies she eats, so JOI-chan wants to know, for each j (1 ≤j ≤⌈N 2 ⌉), the maximum sum of deliciousness of candies when she eats j candies. Here ⌈x⌉is the smallest integer larger than or equal to x. Task Given the number of candies and the deliciousness of candies, write a program which calculates, for each j (1 ≤j ≤⌈N 2 ⌉), the maximum sum of deliciousness of candies when she eats j candies. Input Read the following data from the standard input. • The first line of input contains an integer N. This means there are N candies on the table. • The i-th line (1 ≤i ≤N) of the following N lines contains an integer Ai. This means the deliciousness of the candy which is located i-th from the left is Ai. Output Write ⌈N 2 ⌉lines to the standard output. The j-th line (1 ≤j ≤⌈N 2 ⌉) of output contains the maximum sum of deliciousness of candies when she eats j candies. Constraints All input data satisfy the following conditions. • 1 ≤N ≤200 000. • 1 ≤Ai ≤1 000 000 000 (1 ≤i ≤N). Candies– 1 / 3 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 4 – Candies Subtask There are 2 subtasks. The score and additional constraints of each subtask are as follows: Subtask 1 [8 points] • N ≤2 000. Subtask 2 [92 points] There are no additional constraints. Sample Input and Output Sample Input 1 Sample Output 1 5 7 3 12 5 10 1 7 6 In Sample Input 1, there are 5 candies and their deliciousness are 3, 5, 1, 7, 6 from the left. JOI-chan should eat candies as follows: • When she eats 1 candies, she eats fourth candy from the left (deliciousness 7). • When she eats 2 candies, she eats second and fourth candies from the left (deliciousness 5, 7). • When she eats 3 candies, she eats first and third and fifth candies from the left (deliciousness 3, 1, 6). Again, she cannot choose two consecutive candies simultaneously. For example, keep in mind that when she eats 2 candies, she cannot eat both fourth and fifth candies from the left (deliciousness 7, 6). Candies– 2 / 3 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 4 – Candies Sample Input 2 Sample Output 2 20 936349374 623239331 1855340557 125587558 2763350783 908010226 3622744640 866053126 4439368364 389255266 5243250666 859393857 5982662302 596640443 6605901633 60521559 7183000177 11284043 7309502029 930138174 936349374 810093502 521142682 918991183 743833745 739411636 276010057 577098544 551216812 816623724 Candies– 3 / 3