#include <vector>
#include <iostream>
using namespace std;
vector<int> tri; // Запас треугольных чисел :)
long long res[2019][65];
// Рекурсивный вызов, изначально - доступны все числа (k)
long long getThree(int n, int k = tri.size()-1)
{
if (n < 0 || k < 0) return 0;
if (k == 0)
{
if (n == tri[k]) res[n][k] = 1;
if (n == 0) res[n][k] = 1;
}
else if (n == 0) res[n][k] = 1;
if (res[n][k] == -1)
{
res[n][k] = getThree(n-tri[k],k-1) + getThree(n,k-1);
}
return res[n][k];
}
int main(int argc, const char * argv[])
{
// Заполняем массив треугольными числами
for(int i = 1; i <= 64; ++i) tri.push_back(i*(i+1)/2);
for(int i = 0; i < 2019; ++i)
for(int j = 0; j < 65; ++j)
res[i][j] = -1;
// Приступаем...
cout << getThree(2018) << endl;
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvcjxpbnQ+IHRyaTsgICAgICAvLyDQl9Cw0L/QsNGBINGC0YDQtdGD0LPQvtC70YzQvdGL0YUg0YfQuNGB0LXQuyA6KQpsb25nIGxvbmcgcmVzWzIwMTldWzY1XTsKCi8vINCg0LXQutGD0YDRgdC40LLQvdGL0Lkg0LLRi9C30L7Qsiwg0LjQt9C90LDRh9Cw0LvRjNC90L4gLSDQtNC+0YHRgtGD0L/QvdGLINCy0YHQtSDRh9C40YHQu9CwIChrKQpsb25nIGxvbmcgZ2V0VGhyZWUoaW50IG4sIGludCBrID0gdHJpLnNpemUoKS0xKQp7CiAgICBpZiAobiA8IDAgfHwgayA8IDApIHJldHVybiAwOwogICAgaWYgKGsgPT0gMCkKICAgIHsKICAgICAgICBpZiAobiA9PSB0cmlba10pIHJlc1tuXVtrXSA9IDE7CiAgICAgICAgaWYgKG4gPT0gMCkgcmVzW25dW2tdID0gMTsKICAgIH0KICAgIGVsc2UgaWYgKG4gPT0gMCkgcmVzW25dW2tdID0gMTsKCiAgICBpZiAocmVzW25dW2tdID09IC0xKQogICAgewogICAgICAgIHJlc1tuXVtrXSA9IGdldFRocmVlKG4tdHJpW2tdLGstMSkgKyBnZXRUaHJlZShuLGstMSk7CiAgICB9CiAgICByZXR1cm4gcmVzW25dW2tdOwp9CgppbnQgbWFpbihpbnQgYXJnYywgY29uc3QgY2hhciAqIGFyZ3ZbXSkKewogICAgLy8g0JfQsNC/0L7Qu9C90Y/QtdC8INC80LDRgdGB0LjQsiDRgtGA0LXRg9Cz0L7Qu9GM0L3Ri9C80Lgg0YfQuNGB0LvQsNC80LgKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gNjQ7ICsraSkgdHJpLnB1c2hfYmFjayhpKihpKzEpLzIpOwogICAgZm9yKGludCBpID0gMDsgaSA8IDIwMTk7ICsraSkKICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgNjU7ICsraikKICAgICAgICAgICAgcmVzW2ldW2pdID0gLTE7CgogICAgLy8g0J/RgNC40YHRgtGD0L/QsNC10LwuLi4KICAgIGNvdXQgPDwgZ2V0VGhyZWUoMjAxOCkgPDwgZW5kbDsKfQoK