I just got AC for this dynamic programming problem 401D - Roman and Numbers after many TLEs, WAs and trials using recursion then loops..
I have faced some behaviour, which -in my opinion- seems to be strange, and I can't figure out why it behaves like that:
Declaring the dp array like this :
dp[1<<18]gives a TLE. However,
long longfor bitmask is slower than
int!!! .... I know that 32bit integer would be sufficient for this problem, but I thought it would be safer to use
I hope someone can explain it for me, thanks a lot :D