mapping pairs

[rjohansson]

Hi,

The code below works fine although a bit slow. In the function P I use a map m from int to long long to cache already calculated function values. However, I would prefer to map the arguments (n, k) directly to the function value without first transforming it to a single int (w = 1000 * n + k). I tried to do it with

map<vector<int, int>, long long>

but it turned out to be painfully slow. How should this be done? I'm grateful for any helpful suggestions on this code.

Cheers, Robert

#include <iostream>
#include <map>

using namespace std;

map<int, long long> m;

long long P(int n, int k){
	if (n < k){return 0;}
	if (n == k){return 1;}
	int w = 1000 * n + k;
	if (m.count(w) == 0){m[w] = P(n - k, k + 1) + P(n, k + 1);}
	return m[w];
}

int main()
{
	int N;
	cin >> N;
	cout << P(N, 1) << endl;
	return 0;
}