All submissions for this problem are available.
Freakin' news has recently claimed that they have discovered a civilization on mars and that they have established contact with the martians. Following is a summary of the dinner hour breakin' news on freakin' news :
So, the thief with the knapsack has entered the house. But this time, the setting for the theft is mars. Martian homeowners are weird. In this particular house, there are n objects numbered from 1,2,...n. Object has a weight w[i] and potential value v[i]. The capacity of the knapsack the theif is carrying is C. The theif wants to select a subset of the objects whose resale value is maximum and whose weight is atmost C.
In a martian home, each object has preobjects without which it is dysfunctional. It is guaranteed that
A] Every object has either 1 or 0 preobjects.
B] No object is a preobject of itself.
C] There is no cyclic preobject dependency.
i.e. There does not exist a sequence of objects a,a,...a[n] such that a[i] is a preobject of a[i+1] for all i, 1<=i<=n-1 and a[n] is a preobject of a.
Following is a peculiarity of the resale value of an object on mars : The resale value of an object i in the selected subset equals its potential value v[i] if and only if its preobject (if any) is included in the selected subset and the resale value of the preobject equals its potential value. Otherwise, the resale value of that object is zero.
(Note : The resale value of an object in the selected subset with no preobjects is always equal to its potential value.)
(Note : The resale value of an object in the selected subset is a function of the selected subset and the potential value of that object.)
The thief has asked freakin' news to find the maximum attainable resale value. Your job is to do this task for freakin' news.
There are n objects numbered 1,2,...n. Object i has non-negative weight w[i] and a non-negative value v[i]. The knapsack has a weight capacity C.
Given a directed acyclic graph G with these objects as vertices. The in-degrees of the vertices are all 0 or 1.
If there is a path from object A to object B in G then A is said to be a pre-requisite of B.
If S is a subset of the objects and i is an object belonging to S, then the resale value of object i wrt S is
v[i] : if all pre-requisites of i belong to S.
0 : otherwise.
The resale value of a subset S of the objects is the sum of values of all its elements wrt S.
The weight of a subset S of the objects is the sum of weights of all its elements.
The objective is to pick a subset S of the objects so that its weight is atmost W and its resale value is the maximum possible. Only the maximum value is to be found and not the set S.
The first line of input contains two space seperated integers - n (the number of objects) and C (the capacity of the knapsack).
The second line contains n space seperated non-negative integers w, w, ... w[n] : the weights of the objects.
The third line contains n space seperated non-negative integers v, v, ... v[n] : the values of the objects.
The fourth line contains n space seperated non-negative integers p, p, ... p[n] which describe the preobjects of the objects. If p[i]=0, object i has no preobject. Otherwise, the preobject of object i is p[i].
The only line of output contains a single integer : the maximum attainable resale value.
10 10 10
5 8 12
0 1 1
Since the weights are all same in this case, we have to select 2 of the 3 objects to be carried in the knapsack. Here is a list of all possibilities of selecting 2 objects:
Objects 1 and 2 : Resale Value : 13
Objects 1 and 3 : Resale Value : 17
Objects 2 and 3 : Resale Value : 0 (since 1 is the preobject of both 2 and 3 and 1 is not selected)
|Time Limit:||0.857271 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.