Cod sursa(job #1223682)

Utilizator MaarcellKurt Godel Maarcell Data 28 august 2014 16:16:07
Problema 1-sir Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
#define MAXS 32640
#define MAXN 255
#define prim 194767
using namespace std;

int N,S, dp[2][2*MAXS+10][MAXN*2+10]; bool l;

int main(){
    ifstream in("1-sir.in");
    ofstream out("1-sir.out");
    in >> N >> S;

    dp[0][MAXS][MAXN]=1;
    int i,j,MAX=0,k;
    for (i=2; i<=N; i++){
        l=!l;
        MAX+=(i-1);
        for (j=-MAX; j<=MAX; j++)
            for (k=-(i-1); k<=(i-1); k++)
                dp[l][j+MAXS][k+MAXN]=(dp[!l][j-k+MAXS][k-1+MAXN]+dp[!l][j-k+MAXS][k+1+MAXN])%prim;
    }

    int res=0;
    for (i=-(N-1); i<=N-1; i++){
        res+=dp[l][MAXS+S][MAXN+i];
        res%=prim;
    }

    out <<res;
    return 0;
}