fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define Samurai ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  5. #define pr_g priority_queue<pair<ll,int>, vector<pair<ll,int>>,greater<pair<ll,int>>>
  6. int dx [] = {0, 0, 1, -1, 1, 1, -1, -1};
  7. int dy [] = {-1, 1, 0, 0, -1, 1, 1, -1};
  8. const double PI = acos(-1.0);
  9. #define el '\n'
  10. const ll mod = 1e9, N = 5e5 + 5, OO = 0x3f3f3f3f;
  11.  
  12.  
  13. void solve(){
  14.     ll n, k; cin >> n >> k;
  15.  
  16.     if (k > n) return void (cout << 1);
  17.  
  18.     vector<ll> v(n + 1, 0), p(n + 1, 0);
  19.     for (int i = 0; i < k; i++){
  20.         v[i] = 1;
  21.         p[i] = v[i];
  22.         if(i > 0) p[i] += p[i - 1];
  23.     }
  24.  
  25.     for (int i = k; i <= n; i++) {
  26.         v[i] = (p[i - 1] - p[i - k - 1])%mod;
  27.         p[i] = v[i];
  28.         p[i] += p[i - 1];
  29.     }
  30.  
  31.     cout << v[n]%mod;
  32. }
  33.  
  34. int main() { Samurai
  35.     int _t = 1; //cin >> _t;
  36.     for (int i = 1; i <= _t; i++){
  37.         solve();
  38.     }
  39.     return 0;
  40. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/vG0mi1
language:
C++ (gcc 8.3)
created:
13 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!