# Untitled

unknown
plain_text
a month ago
1.8 kB
34
Indexable
Never
```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;

}
};```