ALCATRAZ2 - GO GOA GONE
So, it was winter and Me and 8 of my friends decided to plan a trip to GOA. Since the Bars and Clubs are too Expensive out there, we decided to pool money together for our whole trip expenses. Now since every group has some internal politics going on, same applies to our group also :P. 2 Members that are having a cold war between them won't go to the trip if the other one is going. But Since we want to enjoy a lavish party, we want to maximize the pooled money. So, for this task I've chosen my marwari friend Mohit to solve this problem (He's good at money matters). Your task is to help Mohit achieve the maximum pooled money.
Input
First Line will contain 8 space separated integers denoting the money contributed by each member in order.
The next line will contain the total number of pairs having a cold war in between them. Let us denote this by P.
The next P lines will contain 2 numbers separated by a space showing the members having a cold war. Numbers used to denote members will be (1 - 8) for each of the 8 members.
Constraints
Everything is guaranteed to easily fit in 32 bit integer type.
Output
Output will give the maximum amount of money that can be pooled.
Example
Input: 3 14 5 2 3 4 1 9 4 1 2 2 3 4 5 7 8 Output: 30
hide comments
abexcorp:
2024-01-25 23:57:46
SIGABRT in C#, same program in C++ passes without issues. |
|
meatcode:
2022-10-04 06:17:47
Input:
|
|
joe201810a:
2021-12-12 23:27:14
no comment |
|
adarsh_raj:
2020-12-23 07:28:54
Can this be solved using graph coloring?
|
|
scriptkiddiec:
2020-09-03 09:38:02
suppose money contributed by 1 and 3 respectively are 8 and 9.
|
|
conprauser20:
2020-07-08 17:26:20
Something might be wrong with the input, with Kotlin i got NZEC, though with C the same solution got accepted.. |
|
dante_part_2:
2020-05-15 08:54:53
Nice problem Last edit: 2020-05-15 08:55:30 |
|
the_pythor:
2020-05-12 13:56:02
Easy solution as the given constraints are very less. Just generated all the possibilities using recursion. We can do the same thing using Bitmask. |
|
satya1998:
2020-05-01 19:28:46
Using bitmasking. Last edit: 2020-05-01 19:53:22 |
|
nadstratosfer:
2020-02-06 23:06:24
mostafiz_53: Optimal selection is 2 (even though that means neither 1 nor 3 can go), 5 (this eliminates 4), 6 (no conflicts with anyone) and 9. 14+3+4+9 = 30.
|
Added by: | Alcatraz |
Date: | 2016-12-08 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | Own Problem |