qmaruf's blog

By qmaruf, history, 7 years ago, In English

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?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it