text: Queries to count groups of N students possible having sum of ratings within given range | C ++ program for the above approach ; Function to count number of ways to get given sum groups ; Initialise dp array ; Mark all 1 st row values as 1 since the mat [ 0 ] [ i ] is all possible sums in first row ; Fix the ith row ; Fix the sum ; Iterate through all values of ith row ; If sum can be obtained ; Find the prefix sum of last row ; Traverse each query ; No of ways to form groups ; Driver Code ; Given n batches and k students ; Given ratings ; Given Queries ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void numWays ( int ratings [ n ] [ k ] , int queries [ ] [ 2 ] ) { int dp [ n ] [ 10000 + 2 ] ; for ( int i = 0 ; i < k ; i ++ ) dp [ 0 ] [ ratings [ 0 ] [ i ] ] += 1 ; for ( int i = 1 ; i < n ; i ++ ) { for ( int sum = 0 ; sum <= 10000 ; sum ++ ) { for ( int j = 0 ; j < k ; j ++ ) { if ( sum >= ratings [ i ] [ j ] ) dp [ i ] [ sum ] += dp [ i - 1 ] [ sum - ratings [ i ] [ j ] ] ; } } } for ( int sum = 1 ; sum <= 10000 ; sum ++ ) { dp [ n - 1 ] [ sum ] += dp [ n - 1 ] [ sum - 1 ] ; } for ( int q = 0 ; q < 2 ; q ++ ) { int a = queries [ q ] [ 0 ] ; int b = queries [ q ] [ 1 ] ; cout << dp [ n - 1 ] [ b ] - dp [ n - 1 ] [ a - 1 ] << " ▁ " ; } } int main ( ) { #define n  2 NEW_LINE #define k  3 NEW_LINE int ratings [ n ] [ k ] = { { 1 , 2 , 3 } , { 4 , 5 , 6 } } ; int queries [ ] [ 2 ] = { { 6 , 6 } , { 1 , 6 } } ; numWays ( ratings , queries ) ; return 0 ; }