以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 8, 2024
Problem D. Big Persimmon
Input file: standard input
Output file: standard output
Time limit: 2 seconds
Memory limit: 1024 megabytes
Alice and Bob bought a big persimmon, cut it into n pieces with sizes w1, . . . , wn, and immediately started
eating it. The kids will eat the pieces simultaneously, and for each of them, the eating process is as follows:
As soon as someone finishes eating their previous piece (and at the beginning of the meal), they choose
the next piece and start eating it. If a piece of size w is taken, it will take exactly w seconds to eat it, and
then it will be time to choose a new piece. If both finish eating their previous piece at the same time (or
if the eating just started), Alice will choose the first piece, but they will start eating at the same time.
Choosing a new piece does not take time.
Since both Alice and Bob are perfectionists, when they choose a piece, they will take either the smallest
(with the smallest wi) or the largest (with the largest wi) from all the remaining pieces.
The eating process ends when the last person finishes eating and there are no more pieces left.
Both Alice and Bob are interested in eating as much as possible. Find the total size of the pieces that
Alice will eat and the total size of the pieces that Bob will eat, if they both choose the pieces optimally.
Input
The first line contains a single integer n (1 ≤n ≤2000) — the number of persimmon pieces.
The second line contains n integers w1, w2, . . . , wn (1 ≤wi ≤20 000, wi ≤wi+1) — the sizes of the
persimmon pieces.
Let W denote the sum of the sizes of all the pieces. It is guaranteed that W ≤20 000.
Output
In a single line, output two numbers — the total size of the pieces that Alice will eat and the total size of
the pieces that Bob will eat, if they both choose the pieces optimally.
Examples
standard input standard output
5 8 7
1 1 3 4 6
4 3 3
1 1 2 2
4 10 14
1 7 7 9
Note
In the first example, Alice should first take a piece of size 1. Immediately after that, Bob should also take
a piece of size 1. After a second, Alice will take a piece of size 3, and then Bob will take a piece of size 6.
3 seconds later, Alice will take a piece of size 4. 3 seconds later, Bob will finish eating, and a second later
the process will finish. At this point, Alice will eat pieces of sizes 1 + 3 + 4 = 8, and Bob: 1 + 6 = 7.
In the third example, Alice should take a piece of size 1, and Bob should take a piece of size 7. After a
second, Alice will take a piece of size 9, and 6 seconds later, Bob will take a piece of size 9.
Scoring
The tests for this problem consist of four groups. Points for each group are awarded only when all the
Page 11 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 8, 2024
tests of the group and some of the tests of the previous groups are passed. Note that passing the example
tests is not required for some groups. Offline-evaluation means that the results of testing your solution
on this group will only be available after the competition.
Additional constraints Required
Group Points Comment
Groups n wi
0 0 – – – Examples.
1 10 n = 3 – – –
2 12 – wi ≤2 – –
3 19 n ≤200 wi ≤500 0 –
4 15 n ≤500 W ≤5000 – wi+1 ≤2 · wi for all 1 ≤i ≤n −1
5 13 – – 2, 4 wi+1 ≤2 · wi for all 1 ≤i ≤n −1
6 31 – – 0 – 5 Offline-evaluation.
Page 12 of 12