Untitled

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        int n = nums.size();
        long long mod = (1e9 + 7)*1LL;
        
        long long dp[n + 1][1010], pref[n + 1][1010];
        memset(dp, 0, sizeof(dp));
        memset(pref, 0, sizeof(pref));
        
        for(int j = 0 ; j <= nums[0] ; j++){
            dp[1][j] = 1*1LL;
            pref[1][j] = dp[1][j];
            if(j > 0)
            pref[1][j] += pref[1][j - 1];
        }
        
        for(int i = 2 ; i <= n ; i++){
         //  cout<<"okay i "<<i<<endl;
            for(int j = 0 ; j <= nums[i - 1] ; j++){
                if(j > 0)
                pref[i][j] = pref[i][j - 1];
                int z = nums[i - 1] - j;
                
                int lo = 0, hi = j;
                int sweetspot = -1;
                
                while(lo <= hi){
                    int mid = (lo + hi) / 2;
                    int z1 = nums[i - 2] - mid;
                    if(z1 >= z){
                        sweetspot = mid;
                        lo = mid + 1;
                    }
                    else{
                        hi = mid - 1;
                    }
                }
                
                //cout<<"okay for j: "<<j<<"  "<<sweetspot<<endl;
                
                if(sweetspot != -1){
                    dp[i][j] = pref[i - 1][sweetspot];
                    dp[i][j] %= mod;
                }
                pref[i][j] += dp[i][j];
                pref[i][j] %= mod;
                
            }
            
        }

        long long ans = 0;
        
        for(int j = 0 ; j <= nums[n - 1] ; j++){
            ans += dp[n][j];
            ans %= mod;
        }
        
        return ans;
        
    }
};