.. wrote:My algorithm has runtime O(n * 3^s). As I want to reduce the memory usage, I use 2 pieces of 3^s memory, on start of very loop I copy one to another(I guess you know what I say...

O(n*3^s) here...... but it gets faster and with less memory as it goes bottom up using just one table size (3 ^ s). Just a little bit of memory needed...

But then, if you use the (3^s) * 2 table, you can always use a trick a friend of mine tought me:

int actual = 0;
int other = 1;
for(i -> n) {
// do your stuff, reading from "actual" and writing to "other"
// after everything is done, change their values
actual = !actual;
other = !other;
}
// at the end, you have the result on table 'ACTUAL'

So you dont have to copy the data from one to the other everytime

Thanks for the sample i/o. It confirmed what I thought, I've misunderstood the problem. I thought that there had to be at least one serving teacher and at least one applicant for each subject. Since there is no serving teacher for subject 4 in the first input above, my program finds no solution. But why is the answer 58000, and not 56000 (using 1000 1 2, 5000 1 2 3 4 and 50000 3 4)? What is the difference between a serving teacher and an applicant in this problem? Is the difference above due to the fact that serving teachers always must be chosen? I hope someone can explain...

It seems the thinking needed to write the above post helped me a lot! Of couse the serving teachers are employed at the school and they are always chosen . I just got accepted. Btw, I use only one 3^n table, it's possible when reversing the inner loop (counting down instead of up) in the DP.

Can somebody explain me how to get:
a) time complexity O(n*4^s)
b) time complexity O(n*3^s)

I have O(n*s*2^(2s)) for each masc 'M' I must compute the set 'S' for actual applicant than I can substract from this masc min(dp[M], dp[M-S]). I cannot compute 'S' at the begining of processing actual applicant because it depends on masc 'M' wheter in some subjects applicant is a first or second teacher.