fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ff first
  4. #define ss second
  5. #define vpl vector<pair<ll,ll>>
  6. #define vll vector<ll>
  7. #define vvl vector<vector<ll>>
  8. #define speed ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  9. #define ison(x,k) ((x)&(1ll<<k))
  10. #define onit(x,k) (x=(x|(1ll<<k)))
  11. #define ofit(x,k) (x=(x^((1ll<<k))))
  12. #define hbit(e,x)  (e=(64ll)-__builtin_clzll(x))
  13. #define mod (ll)(1e9+7)
  14. #define oo 0x3f3f3f3f3f3f3f3f
  15. #define endl "\n"
  16. const ll N = 1e5 + 7;
  17. using namespace std;
  18. using namespace chrono;
  19. ll n, k;
  20. int dp[101][N];
  21. vll v;
  22. vll pre;
  23. ll go(ll i,ll j) {
  24.     if (i == n) {
  25.         if (j == 0) return 1;
  26.         else return 0;
  27.     }
  28.     if (j == 0) return 1;
  29.     if (~dp[i][j]) return dp[i][j];
  30.     ll ch2 = 0;
  31.     ll sum = pre[n - 1] - (i ? pre[i - 1] : 0);
  32.     ll o = j - sum;
  33.     if (o > 0) return 0;
  34.     for (ll k1 = 0; k1 <= min(v[i], j); k1++) {
  35.         ch2 += go(i + 1, j - k1);
  36.         if (ch2 >= mod) ch2 -= mod;
  37.     }
  38.     return dp[i][j] = (ch2) % mod;
  39. }
  40.  
  41. void solve(int tttt) {
  42.     cin >> n >> k;
  43.     memset(dp, -1, sizeof(dp));
  44.     for (ll i = 0; i < n; i++) {
  45.         ll x;
  46.         cin >> x;
  47.         v.push_back(x);
  48.     }
  49.     pre = v;
  50.     for (ll i = 1; i < v.size(); i++) {
  51.         pre[i] = pre[i - 1] + pre[i];
  52.     }
  53.     cout << go(0, k) << endl;
  54. }
  55.  
  56. int main() {
  57. #ifndef ONLINE_JUDGE
  58.     freopen("input.txt", "r",stdin);
  59.     freopen("output.txt", "w",stdout);
  60.     freopen("time.txt", "w",stderr);
  61. #endif
  62.     auto start = high_resolution_clock::now();
  63.     speed;
  64.     ll TC = 1; //cin>>TC;
  65.     for (int i = 1; i <= TC; i++) solve(i);
  66.     auto end = high_resolution_clock::now();
  67.     auto duration = duration_cast<milliseconds>(end - start);
  68.     cerr << "time = " << duration.count() << " ms" << endl;
  69.     auto duration_sec = duration_cast<seconds>(end - start);
  70.     cerr << "time = " << duration_sec.count() << " s" << endl;
  71. }
  72.  
Success #stdin #stdout #stderr 0.01s 43012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
time = 6 ms
time = 0 s
https://ideone.com/hXf56m
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!