#include <vector>
#include <algorithm>
#include <iostream>

int width;
int blockSize;
static std::vector<double> memoize;

double pStdCap(int n, int m, int myMax) {
    
    if (myMax * m < n || n < m) return 0;
    if (myMax * m == n || n <= m + 1) return 1;
    if (m < 2) return m;
    
    const int block = myMax * blockSize + (n - m) * width + m - 2;
    if (memoize[block]) return memoize[block];
    
    int niter = n / m;
    
    if (m == 2) {
        if (myMax * 2 >= n) {
            myMax = std::min(myMax, n - 1);
            return niter - (n - 1 - myMax);
        } else {
            return 0;
        }
    }
    
    double count = 0;
    
    for (; niter--; n -= m, --myMax) {
        count += (memoize[myMax * blockSize + (n - m) * width + m - 3] = pStdCap(n - 1, m - 1, myMax));
    }
    
    return count;
}

double CountPartLenCap(int n, int m, int myMax) {
    
    if (myMax * m < n || n < m) return 0;
    if (myMax * m == n || n <= m + 1) return 1;
    if (m < 2) return m;
    
    if (m == 2) {
        if (myMax * 2 >= n) {
            myMax = std::min(myMax, n - 1);
            return n / m - (n - 1 - myMax);
        } else {
            return 0;
        }
    }
    
    width = m;
    blockSize = m * (n - m + 1);
    memoize = std::vector<double>((myMax + 1) * blockSize, 0.0);
    
    return pStdCap(n, m, myMax);
}

int main() {
	std::cout << "Here are the 5 4-length partitions of 10 with a max of 4\n";
	std::cout << "1, 1, 4, 4\n1, 2, 3, 4\n";
	std::cout << "1, 3, 3, 3\n2, 2, 2, 4\n";
	std::cout << "2, 2, 3, 3\nThe function properly returns 5\n";
	std::cout << CountPartLenCap(10, 4, 4) << std::endl;
	std::cout << "The function instantly returns the number of 15-length partitions of 100 with a max of 15\n";
	std::cout << CountPartLenCap(100, 15, 15) << std::endl;
	std::cout << "While the below computes without exceeding the time limit, it probably isn't very useful\n";
	std::cout << CountPartLenCap(10000, 40, 300) << std::endl;
	return 0;
}