fork download
copy 
  1. #pragma GCC optimize("Ofast,O3,unroll-loops")
  2. #include <bits/stdc++.h>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #define bp __builtin_popcountll
  5. #define mp make_pair
  6. #define pb push_back
  7. #define vec vector
  8. #define ll long long
  9. #define F first
  10. #define S second
  11. #define pii pair <int, int>
  12. #define elif else if
  13. #define sz(a) int32_t(a.size())
  14. #define lb lower_bound
  15. #define ub upper_bound
  16. #define all(a) a.begin(), a.end()
  17. #define fl fflush(stdout)
  18. #define ex exit(0)
  19. #define int ll
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22. template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  23. mt19937 rnd(878787);
  24. mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  25. const int N = 1e6 + 5;
  26. const int mod = 1e9 + 7;
  27. int n, m;
  28. ll dp[N], sum[N];
  29.  
  30. main(){
  31.     ios_base::sync_with_stdio(0);
  32.     cin.tie(0); cout.tie(0);
  33.  
  34.     cin >> n >> m;
  35.  
  36.     dp[0] = 1;
  37.  
  38.     for(int i = 1; i <= n; ++i){
  39.  
  40.         for(int j = 0; j <= m; ++j){
  41.             if(j != 0) sum[j] = sum[j - 1];
  42.             sum[j] += dp[j];
  43.             sum[j] %= mod;
  44.         }
  45.  
  46.         for(int j = m; j >= 0; --j){
  47.             int val = 0;
  48.             if(j - i >= 0) val = sum[j - i];
  49.             dp[j] = (sum[j] - val + mod) % mod;
  50.         }
  51.         for(int j = m; j >= 0; --j) sum[j] = 0;
  52.  
  53.  
  54.     }
  55.  
  56.     cout << dp[m] % mod;
  57. }
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/kLkpPi
language:
C++ (gcc 8.3)
created:
203 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!