The following code generates different result for input "54 60 16" for this problem http://codeforces.com/contest/431/problem/C
PC output: 931055544
Online judge output: 811386435
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll MOD = 1000000007;
ll n, k, d;
ll mem[101][2];
ll solve(ll cursum, int exist)
{
if(mem[cursum][exist]!=-1)return mem[cursum][exist];
if(cursum == n)return (ll)exist;
if(cursum > n)return 0L;
ll ans = 0L;
for(ll b = 1; b <= min(k, n); b++)
{
ans = (ans + solve(cursum + b, exist|(b>=d)))%MOD;
}
mem[cursum][exist] = ans;
return ans;
}
int main()
{
while(cin>>n>>k>>d)
{
memset(mem, -1, sizeof(mem));
ll res = solve(0, 0);
cout<<res<<endl;
}
return 0;
}
Am I missing anything?
may be because of memset memset for 2-d array should be like this
memset(mem, -1, sizeof(mem[0][0])*101*2);sizeof(mem)will return exactly size of array, same as you wrote. Don't confuse that with takingsizeofpointer, which is typically a mistake.i read it here and here
I don't say it's incorrect, I'm just pointing out to another possbility.
Your program contains undefined behavior: it's possible that you access memory out of the
memarray. Ifcursum > n, your function will return, but first it will read value frommem[cursum][exist], which is undefined behavior ifcursum > 100.Single undefined behavior of any kind makes your program's behavior undefined as well. Reasoning: compilers can do really cool (or weird) optimizations assuming that there is no undefined behavior. And when it happens, anything can happen and you cannot simply predict what exactly.
Same problem for this submission: 137826674. I get correct output on my computer (NO YES NO NO YES YES), but on online judge it's all just YES.