All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Broken Amit

Algorithms, Bitmask, Dynamic Programming


It has been truly said that love is not meant for everyone.

Let me introduce you to a very sad story of my friend Broken Amit. Yes several times he has been left heartbroken. Looking at his poor condition even God is pity on him. God has given Amit a very nice opportunity to Kiss as many girls as he likes .

There are N number of girls each having a "Love value" as well as a decrement value.

So, Amit needs to kiss all the N girls exactly once in some order.

In one step, he can kiss only a single girl and after every step girl's "Love value" decreases by an amount equal to her decrement value times her index (indexing starts from 0) . But once a girl has been kissed her "Love value" won't decrease in further steps.

"Love value" for Amit in a particular step is equal to the sum of "Love values" of all the n girls before the beginning of that step, whereas the "Gross Love Value" of Broken Amit is sum of "Love Values" for Amit in each step.

Now Amit not being a good analyzer wants your help to find the maximum "Gross Love Value" he can earn.


First line contains an integer N - denoting the number of girls.

Second line contains N integers denoting the initial "Love value" of the girls (L[i]).

Third line contains N integers denoting the "decrement value of the girls (D[i]).


Single integer denoting maximum "Gross Love Value", Broken Amit can earn.


1 <= n <= 17

0 <= L[i] < 500000

0 <= D[i] < 500000

2 4
1 2

If Amit kisses the first girl and then the 2nd one - 1st step - 2 + 4 = 6 2nd step - 2 + (4 - 12) = 4 Gross Love Value - 6+4 = 10 If Amit kisses the 2nd girl than the 1st one. 1st step - 2 + 4 = 6 2nd step - (2 - 01) + 4 = 6 Gross Love Value = 12

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications