Kralj
레이팅 미적용의견: 0
2 \(s / 128\) \(MB / 140\) points
Young ruler Mirko has declared himself king of dwarves. Upon hearing this, Slavko felt
threatened and soon declared himself king of elves! As there cannot be more than one king
in the land, they have decided to resolve the issue of power once and for all.
Slavko will, along with \(N\)
strongest elves of the kingdom, labeled with numbers from 1 to \(N\)
,
go visit Mirko’s castle. In the castle hall, they will be greeted by \(N\)
strongest dwarves sitting
in a circle, labeled clockwise with numbers from 1 to \(N\)
.
Mirko has, upon entering the castle, given a number \(A\)
\(i\)
to each of Slavko’s elves – the label
of the dwarf it will fight against. Unfortunately, he didn’t make sure that each elf should get a
unique adversary, and soon a terrible fight broke out.
They have decided to solve the problem in the following way:
●
Slavko will send his elves to the hall one by one, in the order he chooses. The next
elf can enter the hall only after the one before him found a place to sit.
●
The elf labeled \(k\)
will first approach the dwarf labeled \(A\)
\(k\)
.
If there isn’t an elf sitting
beside the dwarf, he will sit there. Otherwise, he will continue walking, from dwarf to
dwarf, clockwise, until he finds an unclaimed dwarf.
Now the \(N\)
resulting pairs of elves and dwarves compete in armwrestling, and the stronger
one always wins .
Slavko is well prepared for this event. He has studied all the fighters and determined the
strength of each one. Now he wants to send the elves to the hall in the order which, after
they all sit down, will bring the most victories for him.
Help him and calculate the highest number of victories in duels that can be achieved by
elves !
In test cases worth 40% of total points, Mirko will choose the dwarf labeled with 1 ( \(A\)
\(i\)
= 1 for
each \(i\) from 1 to \(N\)) as an adversary in each elf duel.
The first line of input contains the integer \(N\)
(1 ≤ \(N\)
≤ \(5 \cdot 10\) {5}{ })
The second line of input contains \(N\)
integers \(A\)
\(i\)
(1 ≤ \(A\)
\(i\)
≤ \(N\)
), the adversaries chosen by Mirko.
The third line of input contains \(N\)
integers \(P\)
\(i\)
(1 ≤ \(P\)
\(i\)
≤ 10 {9}{ }), the dwarves’ strengths.
The fourth line of input contains \(N\)
integers \(V\)
\(i\)
(1 ≤ \(V\)
\(i\)
≤ 10 {9}{ }), the elves’ strengths.
All strengths from the input will be mutually distinct.
The first and only line of input must contain the maximum number of victories that can be
achieved by elves.
2 \(s / 128\) \(MB / 140\) points
3
2 3 3
4 1 10
2 7 3
4
3 1 3 3
5 8 7 10
4 1 2 6
3
1 2 3
8 4 3
9 2 6output
output
2
1
2Clarification of the first test case:
Slavko can sort the elves in the following way: 3, 2, 1. This way, the elf number 3 will sit beside dwarf
number 3, elf 2 will have to move one seat clockwise and sit beside dwarf 1, and the elf number 2 will sit
beside the dwarf number 2. Elves 1 and 2 will win their duels, and elf 3 will lose.
평가 및 의견
Kralj
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Kralj