Cod sursa(job #1090971)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 23 ianuarie 2014 13:18:07
Problema 1-sir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>
#define MOD 194767

using namespace std;

int dp[258][66050];

int main()
{
    int i,j,N,S;
    freopen ("1-sir.in","r",stdin);
    freopen ("1-sir.out","w",stdout);
    scanf("%d%d", &N,&S);
    if(S<0)
        S=-S;
    if(S>((N-1)*N)/2)
        printf("0\n");
    else
    {
        S=(N*(N-1)/2)-S;
        dp[1][0]=dp[1][2]=1;
        for(i=2;i<N;++i)
            for(j=0;j<=S;++j)
            {
                dp[i][j]=dp[i-1][j];
                if(j>=2*i)
                    dp[i][j]=(dp[i][j]+dp[i-1][j-2*i])%MOD;
            }

        printf("%d\n", dp[N-1][S]);
    }
    return 0;
}