Product owner problem

1

https://devskill.com/CodingProblems/ViewProblem/11
please help in solving this problem

2

I don’t know the exact solution but would like to share my thoughts on this problem.

The Problem statement in a Nutshell:

Given N, M and M pairs of the form (min_i, max_i), your task is to find the number of tuples (x_1,\ x_2,\ \dots,\ x_m) that satisfy the following conditions.

  • min_i\le x_i\le max_i
  • \sum_{i = 1}^{M} x_i = N

Example 1

N = 3, M = 2
The Pairs: (0, 3), (1, 3)

Output: 3
Explanation:
The Solution set is given by:
{(0, 3), (1, 2), (2, 1)}

Example 2

N = 5, M = 3
The Pairs: (0, 2), (1, 3), (2, 3)

Output: 5
Explanation:
The Solution set is given by:
{(0, 2, 3), (0, 3, 2), (1, 1, 3), (1, 2, 2), (2, 1, 2)}

This should be a combinatorics problem (or maybe, a DP problem).
@cubefreak777 may help us.

3
DP_{i,j} \rightarrow \text{Number of ways to have a sum $j$ with first $i$ elements satisfying }\\ \text{$L_i \le x_i \le R_i$ for every $1\le i \le M $}\\
DP_{i,j}=\sum_{k=L_i}^{R_i}DP_{i-1,j-k}

Final answer will be DP_{M,N}

UNTESTED CODE 
#define ONLINE_JUDGE 1
#include "bits/stdc++.h"
using namespace std ;
#define int long long 
const int M=1e9+7 ;
void solve(){
  int n,m  ;
  cin >> n >> m ;
  vector<vector<int>>DP(m+1,vector<int>(n+1)) ; 
  vector<int>l(m+1),r(m+1) ;
  for(int i=1;i<m+1;i++)
    cin >>l[i] >> r[i] ;
  DP[0][0]=1 ;
  for(int i=1;i<m+1;i++){
    for(int j=0;j<n+1;j++){
      for(int k=l[i];k<r[i]+1;k++){
        if(j<k)
          continue  ;
        (DP[i][j]+=DP[i-1][j-k])%=M ;
      }
    }
  }
  cout << DP[m][n] << '\n' ;
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);     
  int TC  ;
  cin >>TC ;
  for(int _=0;_<TC;_++){
    cout << "Case "<<_+1<<": " ;
    solve() ;
  }
}

This stupid judge is not giving a verdict on my solution for 15mins. Do let me know if this fails for some case, I haven’t tested it.