Cod sursa(job #1090973)

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

using namespace std;

int dp[2][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&1)][j]=dp[((i-1)&1)][j];
                if(j>=2*i)
                    dp[(i&1)][j]=(dp[(i&1)][j]+dp[((i-1)&1)][j-2*i])%MOD;
            }

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