Codeforces - Arpa's weak amphitheater and Mehrdad's valuable Hoses

Help me solving THIS PROBLEM from codeforces div-2 I couldn’t solve this problem during the contest.

First find all the connected components, as u can see, u can chhose atmost one or all the nodes/hoses of a particular connected component. Let C1,C2 , … , Ck be the connected components. Now define DP [ I ] [ Wt ] to be the max beauty selecting hoses till the Ci with weight limit (max allowed total weight) Wt. The answer to the problem will be DP [ K ] [ W ] where W is the given number in the problem.

For i from 1 to K, Wt from 1 to W :

To find DP [ I ] [ Wt ]:

  1. U dont choose any hose from component I ( + DP [i-1][Wt] )

  2. U choose all hoses from I ( + DP [ i-1][WT - sum_wt(Ci) ] + sum_beauty(Ci))

  3. iterate thru all hoses in Ci one by one, let X be one of them ( + DP[i-1][wt-weight(X) ] + beauty[X] )

In case 2,3 check that WT - sum_wt(Ci),wt-weight(X) >= 0 .

My code

1 Like


Two Hoses x and y are in the same friendship group if and only if there is a sequence of Hoses a1, a2, …, ak such that ai and ai + 1 are friends for each 1 ≤ i < k, and a1 = x and ak = y.

What does this line mean, and how it will be taken care of in your approach.

this means that x and y are in same connected component of the graph

Thanks, I understood.