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; } };
Leave a Comment