fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define ll long long int
  8. #define s(x) scanf("%d", &x)
  9. #define sd(x) scanf("%lf", &x)
  10. #define sl(x) scanf("%lld", &x)
  11. #define mod 1000000007
  12. #define mod1 1000000006
  13. #define get getchar//_unlocked
  14. #define INF 1000000000000000000LL
  15.  
  16. ll ans[100005];
  17. ll dp[2005][2005];
  18. ll cumDp[2005][2005];
  19. ll a[100005];
  20. ll cumAns[100005];
  21.  
  22. int main()
  23. {
  24.     int t, n, k, i, j, l;
  25.     cin >> t;
  26.     while (t--) {
  27.         cin >> n >> k;
  28.         for (i = 1; i <= k; ++i)
  29.             cin >> a[i];
  30.         for (i = 1; i <= k; ++i) {
  31.             dp[1][i] = 1;
  32.             cumDp[1][i] = 1;
  33.         }
  34.         ans[1] = k;
  35.         cumAns[1] = k;
  36.         for (i = 2; i <= n; ++i) {
  37.             ans[i] = 0;
  38.             for (j = 1; j <= k; ++j) {
  39.                 dp[i][j] = 0;
  40.                 l = max(0LL, i-a[j]);
  41.                 dp[i][j] = cumAns[i-1];
  42.                 if (l)
  43.                     dp[i][j] -= cumAns[l-1];
  44.                 dp[i][j] -= (cumDp[i-1][j]);
  45.                 if (l)
  46.                      dp[i][j] += cumDp[l-1][j];
  47.                 dp[i][j] %= mod;
  48.                 if (dp[i][j] < 0)
  49.                     dp[i][j] += mod;
  50.                 cumDp[i][j] = cumDp[i-1][j] + dp[i][j];
  51.                 if (cumDp[i][j] >= mod)
  52.                     cumDp[i][j] -= mod;
  53.                 if (!l) {
  54.                     ++dp[i][j];
  55.                     ++cumDp[i][j];
  56.                 }
  57.                 if (cumDp[i][j] >= mod)
  58.                     cumDp[i][j] -= mod;
  59.                 if (dp[i][j] >= mod)
  60.                     dp[i][j] -= mod;
  61.                 /*for (l = 1; l <= a[j] && i-l > 0; ++l) {
  62.                     dp[i][j] += ans[i-l];
  63.                     if (dp[i][j] >= mod)
  64.                         dp[i][j] -= mod;
  65.                     dp[i][j] -= dp[i-l][j];
  66.                     if (dp[i][j] < 0)
  67.                         dp[i][j] += mod;
  68.  
  69.                 }
  70.                 if (l <= a[j]) {
  71.                     ++dp[i][j];
  72.                 }*/
  73.                 ans[i] += dp[i][j];
  74.                 //cout << i << " " << j << " " << dp[i][j] << endl;
  75.                 if (ans[i] >= mod)
  76.                     ans[i] -= mod;
  77.             }
  78.             cumAns[i] = cumAns[i-1] + ans[i];
  79.             if (cumAns[i] >= mod)
  80.                 cumAns[i] -= mod;
  81.         }
  82.         cout << ans[n] << endl;
  83.     }
  84.     return 0;
  85. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python2.7/py_compile.py", line 117, in compile
    raise py_exc
py_compile.PyCompileError:   File "prog.py", line 3
    using namespace std;
                  ^
SyntaxError: invalid syntax
stdout
copy 
Standard output is empty
https://ideone.com/uuvjkN
language:
Python (cpython 2.7.16)
created:
7 years ago
visibility:
secret

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!