Advertisement
Josif_tepe

Untitled

Mar 17th, 2021
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include<string>
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 1e5 + 10;
  6. const ll MOD = 1e9 + 7;
  7. ll P, B;
  8. int n;
  9. ll arr[maxn];
  10. int main()
  11. {
  12.     ios_base::sync_with_stdio(false);
  13.     cin >> P >> B;
  14.     cin >> n;
  15.     for(int i = 1; i <= n; i++) {
  16.         cin >> arr[i];
  17.     }
  18.     ll dp[n + 2][n + 2][n + 2] ;
  19.     memset(dp, 0, sizeof dp);
  20.     dp[1][0][0] = 1;
  21.         for(int a = 0; a <= n; a++) {
  22.             for(int b = 0; b <= n; b++) {
  23.                 for(int i = 1; i <= n; i++) {
  24.                     // binary_search
  25.                 int next = (i + 1);
  26.                 int current = (i);
  27.                 if(a == 0 or arr[i] - arr[a] >= P) {
  28.                   // query(i, b) += dp[current][a][b];
  29.                     dp[next][i][b] += dp[current][a][b];
  30.                     if(dp[next][i][b] >= MOD) {
  31.                         dp[next][i][b] -= MOD;
  32.                     }
  33.                 }
  34.                 if(b == 0 or arr[i] - arr[b] >= B) {
  35.                    
  36.                     dp[next][a][i] += dp[current][a][b];
  37.                     if(dp[next][a][i] >= MOD) {
  38.                         dp[next][a][i] -= MOD;
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.     }
  44.     ll ret = 0;
  45. //    cout << dp[0][n][n] << " "<< dp[1][n][n]
  46.     for(int a = 0; a <= n; a++) {
  47.         for(int b = 0; b <= n; b++) {
  48.             ret += dp[n + 1][a][b];
  49.             ret %= MOD;
  50.             cout << dp[0][a][b] << " " << dp[1][a][b] << endl;
  51.         }
  52.     }
  53.     cout << ret << endl;
  54.     return 0;
  55. }
  56. /*
  57.  
  58.  **/
  59.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement