SHARE
TWEET

Untitled

a guest Sep 12th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <set>
  6. #include <map>
  7. #include <unordered_set>
  8. #include <unordered_map>
  9. #include <ctime>
  10. #include <deque>
  11. #include <ctime>
  12. #include <string>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <bitset>
  16. #include <cassert>
  17. #include <cstring>
  18. #include <queue>
  19.  
  20. #define fi first
  21. #define se second
  22. #define ll long long
  23. #define pii pair<int, int>
  24. #define pil pair<int, long long>
  25. #define pli pair<long long, int>
  26. #define pll pair<long long, long long>
  27. #define mp(x, y) make_pair((x), (y))
  28.  
  29. using namespace std;
  30. const ll MOD = 1000 * 1000 * 1000 + 7;
  31. const int MAXSZ = 5e5 + 100;
  32.  
  33. ll stab(ll a) {
  34.     return ((a % MOD + MOD) % MOD);
  35. }
  36.  
  37. int main() {
  38.     freopen("kebab.in", "r", stdin);
  39.     freopen("kebab.out", "w", stdout);
  40.     ios::sync_with_stdio(false);
  41.     cout.tie(0); cin.tie(0);
  42.  
  43.     int n, t;
  44.     cin >> n >> t;
  45.  
  46.     vector<vector<ll>> fdp(301, vector<ll>(301, 0));
  47.     for (int i = 1; i < 301; ++i) {
  48.         fdp[1][i] = 1;
  49.     }
  50.  
  51.     for (int i = 2; i < 301; ++i) {
  52.         for (int l = 2; l < 301; ++l) {
  53.             for (int j = 1; j <= i - t - 1; ++j) {
  54.                 fdp[i][l] += fdp[j][l - 1];
  55.             }
  56.             fdp[i][l] = stab(fdp[i][l]);
  57.         }
  58.     }
  59.  
  60.     array<ll, MAXSZ> dp;
  61.     int cur_s = 1;
  62.     dp[0] = 1;
  63.     for (int i = 0; i < n; ++i) {
  64.         int q, x;
  65.         cin >> q >> x;
  66.  
  67.         for (int j = cur_s; j < cur_s + q; ++j) {
  68.             dp[j] = dp[j - 1];
  69.             for (int l = cur_s; l <= j; ++l) {
  70.                 dp[j] += fdp[j - l + 1][q - x] * dp[max(0, min(cur_s - 1, l - t - 1))];
  71.                 dp[j] = stab(dp[j]);
  72.             }
  73.         }
  74.  
  75.         cur_s += q;
  76.     }
  77.     cout << dp[cur_s - 1] << endl;
  78.    
  79.     r
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top