fork download
copy 
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. vector<int> tri;      // Запас треугольных чисел :)
  7. long long res[2019][65];
  8.  
  9. // Рекурсивный вызов, изначально - доступны все числа (k)
  10. long long getThree(int n, int k = tri.size()-1)
  11. {
  12.     if (n < 0 || k < 0) return 0;
  13.     if (k == 0)
  14.     {
  15.         if (n == tri[k]) res[n][k] = 1;
  16.         if (n == 0) res[n][k] = 1;
  17.     }
  18.     else if (n == 0) res[n][k] = 1;
  19.  
  20.     if (res[n][k] == -1)
  21.     {
  22.         res[n][k] = getThree(n-tri[k],k) + getThree(n,k-1);
  23.     }
  24.     return res[n][k];
  25. }
  26.  
  27. int main(int argc, const char * argv[])
  28. {
  29.     // Заполняем массив треугольными числами
  30.     for(int i = 1; i <= 64; ++i) tri.push_back(i*(i+1)/2);
  31.     for(int i = 0; i < 2019; ++i)
  32.         for(int j = 0; j < 65; ++j)
  33.             res[i][j] = -1;
  34.  
  35.     // Приступаем...
  36.     cout << getThree(2018) << endl;
  37. }
  38.  
  39.  
Success #stdin #stdout 0s 4456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
32090936486947985
https://ideone.com/b6IYzh
language:
C++14 (gcc 8.3)
created:
6 years 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!