Loot of the Rooks
All submissions for this problem are available.
Jacob and evie are the leaders of a gang named ROOKS consisting of n members. Some of the gang members work together in the form of groups.
Each gang member has x money weighing y units.
Each group has to report to jacob with max money of its members . Each group has been alloted a bag weighing a units. Moreover the contribution of the leader in a groups contribution is must(if possible).The leader in a group is person with minimum money and a gang member will either contribute wholly or not in groups collection.
Given list of members who work together. Find the max money jacob can receive collected from all groups
The first line of input contains 3 integers. n a b
n: Number of gang members
a: Max weight alloted to groups
b: Number of people working together
The second line contains an array of n numbers denoting money of each member say A[i]
The third line contains an array of n numbers denoting weight of money each member has , say B[i]
The next b lines contains x and y denoting x and y work together
An integer denoting total max possible money Jacob can recieve
- 1 ≤ n ≤ 100000
- 0 ≤ a ≤ 1000
- 0 ≤ b ≤ 100000
- 0 ≤ A[i],B[i] ≤ 100000
- 1 ≤ x,y ≤ n
Input: 6 8 3 4 5 6 2 1 9 2 3 5 4 7 12 4 5 5 1 2 3 Output: 12
Here are three goups formed (1 4 5) (2 3) ( 6 ) .
From (1 4 5) : 5 is the leader & contribution from this group is 1.
From (2 3) : 2 is the leader & contribution from this group is 11.
From (6) : No contribution is possible.
Hence Total contribution is 12.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.