Check if all people can vote on two machines | C ++ program to check if all people can vote using two machines within limited time ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool canVote ( int a [ ] , int n , int x ) { int dp [ n + 1 ] [ x + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; int sum = 0 ; for ( int i = 0 ; i <= n ; i ++ ) sum += a [ i ] ; for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= x ; j ++ ) if ( a [ i ] <= j ) dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , a [ i ] + dp [ i - 1 ] [ j - a [ i ] ] ) ; else dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; return ( sum - dp [ n ] [ x ] <= x ) ; } int main ( ) { int n = 3 , x = 4 ; int a [ ] = { 2 , 4 , 2 } ; canVote ( a , n , x ) ? cout << " YES STRNEWLINE " : cout << " NO STRNEWLINE " ; return 0 ; }