Check if all people can vote on two machines | Function returns true if n people can vote using two machines in x time . ; dp [ i ] [ j ] stores maximum possible number of people among arr [ 0. . i - 1 ] can vote in j time . ; Find sum of all times ; Fill dp [ ] [ ] in bottom up manner ( Similar to knapsack ) . ; If remaining people can go to other machine . ; Driver Code
def canVote ( a , n , x ) : NEW_LINE INDENT dp = [ [ 0 ] * ( x + 1 ) for _ in range ( n + 1 ) ] NEW_LINE a = a [ : ] NEW_LINE a . append ( 0 ) NEW_LINE sm = 0 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT sm += a [ i ] NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , x + 1 ) : NEW_LINE INDENT if a [ i ] <= j : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , a [ i ] + dp [ i - 1 ] [ j - a [ i ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT return ( sm - dp [ n ] [ x ] ) <= x NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 NEW_LINE x = 4 NEW_LINE a = [ 2 , 4 , 2 ] NEW_LINE print ( " YES " if canVote ( a , n , x ) else " NO " ) NEW_LINE DEDENT