fork(1) download
  1. /****************##### بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم #####********************
  2. __________________________________________________________________________
  3. ###################### Ya-Seen Arafat(ACWizard) #########################
  4. ###################### UAP-CSE-33B #########################
  5. *************************************************************************/
  6. #include <bits/stdc++.h>
  7. #define sc(n) scanf("%d", &n)
  8. #define S 303
  9. using namespace std;
  10. typedef long long LL;
  11.  
  12. int n, low, high;
  13. int make[S];
  14. LL dp[S][S][S];
  15.  
  16. LL Pay(int ind, int tot, int term){
  17. if(term > high)return 0LL;
  18. if(tot < 0)return 0LL;
  19. if(term >= low && term <= high && tot == 0)return 1LL;
  20. if(dp[ind][tot][term] != -1)return dp[ind][tot][term];
  21. dp[ind][tot][term] = 0;
  22. for(int i = ind; i < n; i++){
  23. dp[ind][tot][term] += Pay(i, tot-make[i], term+1);
  24. }
  25. return dp[ind][tot][term];
  26. }
  27.  
  28. void Do(){
  29. string str;
  30. while(getline(cin, str)){
  31. istringstream cinn(str);
  32. int sz = str.size();
  33. int sp = 0;
  34. for(int i = 0; i < sz; i++)if(str[i] == ' ')sp++;
  35. if(sp == 0)cinn >> n, low = 1, high = n;
  36. if(sp == 1)cinn >> n, cinn >> high, low = 1;
  37. if(sp == 2)cinn >> n, cinn >> low, cinn >> high;
  38. for(int i = 0; i < n; i++)make[i] = i+1;
  39. reverse(make, make+n);
  40. memset(dp, -1, sizeof(dp));
  41. cout << Pay(0, n, 0) << endl;
  42. }
  43. }
  44.  
  45. int main(){
  46. ios_base::sync_with_stdio(0); cin.tie(0);
  47. #ifndef ONLINE_JUDGE
  48. ///freopen("inp","r",stdout);
  49. ///freopen("contest.txt","w",stdout);
  50. #endif
  51. Do();
  52. return 0;
  53. }
  54.  
  55.  
  56.  
  57.  
  58.  
Success #stdin #stdout 1.08s 220608KB
stdin
6
6 3
6 2 5
6 1 6
300
300 4 15
200
200 1 200
200 100 150
stdout
11
7
9
11
9253082936723602
5006529163060
3972999029388
3972999029388
1641900823