Sličice
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 90\) points
Nikola is a passionate collector of albums with images of football players. He and his friends compete
with each other in a game they invented based on the albums whose images are currently being
collected. The images in that album are divided into \(N\) teams, each of which has exactly \(M\) football
players. The main rule of the game is that the total number of points a person wins for \(i\) ^{th} team is \(B\) {x}{ },
where \(x\) is the total number of unique pictures of football players of that team collected by the person.
They have also agreed that the array \(B\) is growing, i.e. having more unique images of football players
of a team means having more or equal points.
Nikola would like to win as many points as possible in the game. For each team \(x\) the amount of
unique images Nikola currently owns of that team, \(P\) {x}{ }, is known.
Ivan is a friend of Nikola who has already collected the entire album twice and when he heard about
the game Nikola plays with his friends, he decided to give him any \(K\) images that Nikola wants. After
finding out about this joyful news, Nikola wondered what is the maximal number of points he could
have after Ivan gives him \(K\) images. Too excited for this news, he is not able to count and begs you
to answer his question.
In test samples totally worth 20% of the points it will hold \(K\) = 2.
1 \(s / 64\) \(MB / 90\) points
In the first line there are integer numbers \(N\) , \(M\) and \(K\) (1 ≤ \(N\) , \(M \le 500\), 1 ≤ \(K \le mi\)n( \(N\) · \(M\) , 500)),
numbers from the task's text.
In the second line there is an array \(P\) consisting of \(N\) n\(on-ne\)gative integer numbers (0 ≤ \(P\) {i}{ } ≤ \(M\) ).
In the third line there is an array \(B\) consisting of \(M\) +1 n\(on-ne\)gative integer numbers (0 ≤ \(B\) _{i} ≤100
000), amount of points Nikola gets for \(i\) (0 ≤ \(i\) ≤ \(M\) ) unique images of a team.
For every \(t\) between 0 and \(M-1\) it holds \(B\) {t}{ } ≤ \(B\) {\(t+1\)}{ }.
It is also holds that \(K\) ≤ \(N\) · \(M\) - ( \(P\) {1}{ }+ \(P\) {2}{ }+ ... + \(P\) {N}{ }).
In the only line print the answer to Nikola's question.
4 4 3
4 2 3 1
0 1 3 6 10
4 3 5
1 1 2 3
0 1 2 3
3 6 2
2 4 1
31 38 48 60 75 91 120output
output
31
12
206Clarification of the first sample:
Nikola is most likely to ask Ivan to give him an image of the third team and two from the second, so that his
score is 31 (10 + 10 + 10 + 1).
평가 및 의견
Sličice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Sličice