i am a beginner in dp and have recently learn SOS dp from codeforces …this is my first ques on SOS and has come up with a solution in 5 hours but i am getting WA in the last subtask…(http://ideone.com/tR8gWl) …if possible please look into the code and find the bug!
Link is not working…
the code is fine …the only thing you miss is that you have to calculate the dp array for all the values that can be made from the bits available.i.e. (in your case all the values that can be formed from the ‘bits’ variable i.e. (1 << bits) - 1) . The reason is simple …whenever you are setting a bit you cant guarantee that it lies within that limit (‘maxi’ in your code) …like for example.
suppose you have an array having two elements (1 and 4) . Now, you start your code like…
maxi = 4;
bits = 3;
but, notice that when you reach second or rather the very first bit of 4 (which is not-set) …what you did is copy that left value (the pairs that it can form by placing a set bit there) and then try to add all those pairs that can be made by setting that bit …which is here…all possible pairs of numbers that can be formed from (101 i.e. first bit set) but notice that it is greater than 4 …so, you have a zero at that place rather than a correct value…
so, the only thing you have to do is simply put ‘(1 << bits) - 1’ at the place of ‘maxi’ in the inner loop 
1 Like
thanks bro