CCO '18 P1 - Geese vs. Hawks - Olympiads Online Judge

CCO '18 P1 - Geese vs. Hawks

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 0.6s

Memory limit: 1G

Author:

azneye

Problem type

Canadian Computing Olympiad: 2018 Day 1, Problem 1

Troy and JP are big hockey fans. Every hockey team played $N$ ~N~ games this season. Each game was between two teams and the team that scored more points won. No game ended in a tie.

Troy's favourite team is the Waterloo Geese and he recorded the outcome of all their games as a string $S$ ~S~. $S_i=$ ~S_i=~W if the Geese won their $i$ ~i~-th game; otherwise $S_i=$ ~S_i=~L if the Geese lost their $i$ ~i~-th game. He also recorded that they scored $A_i$ ~A_i~ points in their $i$ ~i~-th game.

JP's favourite team is the Laurier Hawks and he recorded the outcome of all their games as a string $T$ ~T~. $T_j=$ ~T_j=~W if the Hawks won their $j$ ~j~-th game; otherwise $T_j=$ ~T_j=~L if the Hawks lost their $j$ ~j~-th game. He also recorded that they scored $B_j$ ~B_j~ points on their $j$ ~j~-th game.

Troy and JP recorded wins/losses and points in the order that their favourite teams played.

A rivalry game is one where the Geese and Hawks played each other. Since neither Troy nor JP recorded the opponents their favourite teams faced, they are not sure which games, if any, were rivalry games. They wonder what is the maximum possible sum of points scored by both their teams in rivalry games that matches the information they recorded.

Input Specification

The first line contains one integer $N$ ~N~ $(1 \le N \le 1\,000)$ ~(1 \le N \le 1\,000)~.

The second line contains string $S$ ~S~ of length $N$ ~N~ consisting of characters W and L.

The third line contains $N$ ~N~ integers $A_1, \dots, A_N$ ~A_1, \dots, A_N~ $(1 \le A_i \le 1\,000\,000)$ ~(1 \le A_i \le 1\,000\,000)~.

The fourth line contains string $T$ ~T~ of length $N$ ~N~ consisting of characters W and L.

The fifth line contains $N$ ~N~ integers $B_1, \dots, B_N$ ~B_1, \dots, B_N~ $(1 \le B_j \le 1\,000\,000)$ ~(1 \le B_j \le 1\,000\,000)~.

For 10 of the 25 available marks, $N \le 10$ ~N \le 10~.

Output Specification

Print one line with one integer, the maximum possible sum of points scored in potential rivalry games.

Sample Input 1

1
W
2
W
3

Output for Sample Input 1

Explanation for Sample Output 1

Since both the Geese and Hawks won all their games, there could not have been any rivalry games.

Sample Input 2

4
WLLW
1 2 3 4
LWWL
6 5 3 2

Output for Sample Input 2

Explanation for Sample Output 2

The fourth game each team played could have been a rivalry game where Geese won with $4$ ~4~ points to the Hawk's $2$ ~2~ points. The third game the Geese played and the second game the Hawks played could have been a rivalry game where the Hawks won with $5$ ~5~ points compared to $3$ ~3~ points of the Geese. The points scored by both teams is $4+2+5+3=14$ ~4+2+5+3=14~ and this is the maximum possible.

Note that the first game played by the Geese was a win where they scored 1 goal: this game cannot be against the Hawks, since there is no game where the Hawks scored 0 goals. Similarly, the first game played by the Hawks cannot be used, since the Hawks lost and scored 6 goals, and the Geese never had a game where they scored at least 7 goals.

Comments

0

Winbigwok commented on March 29, 2020, 12:28 p.m.

I have the same question Geese: W 4 Hawks: L 2 = 2 + 4 = 6 Geese: L 2 Hawks: W 3 = 2 + 3 = 5 Geese: L 3 Hawks: W 5 = 3 + 5 = 8 Geese: W 1 Hawks: L 6 = not possible

Total should be 19?

1

robem commented on Sept. 16, 2022, 5:01 p.m.

If the Hawks played their 3rd game against the Geese, which were in their 2nd game, then they couldn't have played them previously in the Geese's 3rd game because that's not how time works. You can choose one but not both - given the task, you choose the maximum. In other words, as soon as you match an outcome from the Geese with an outcome from the Hawks, you create a requirement that all previous Hawk games cannot be matched against future Geese games and vice versa. In other words, you have to maintain the order of games.

1

Murk_Zhang commented on Feb. 27, 2020, 8:37 p.m.

for sample 2, shouldn't the game where the geese lost with 2 points and the hawks won with 3 points count as well? So the total points should be 4 + 2 + 5 +3 + 2 + 3 = 19?

0

sushi commented on Feb. 27, 2020, 8:46 p.m.

One of the games was used in another calculation, you are repeating a game. So no.

11

gupta_samarth commented on June 18, 2021, 6:10 a.m.

I would like to point out here, it's not because of the game being reused. It's actually that the scores and results are recorded in order, and hence you can't do something like, match "3rd game of team B with 2nd game of team A" and at the same time match "2nd game of team B with 3rd game of team A".