Cod sursa(job #1213084)

Utilizator tudi98Cozma Tudor tudi98 Data 27 iulie 2014 03:41:58
Problema 1-sir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>
using namespace std;

const int MOD = 194767;
int dp[2][32645];

inline int abs(int a){
    return (a>0?a:-a);
}

int main(){

    freopen("1-sir.in","r",stdin);
    freopen("1-sir.out","w",stdout);

    int n,S;
    scanf("%d %d",&n,&S);
    if(S<0) S-=S<<1;
    if(S>((n-1)*n>>1)) printf("0\n");
    else{
        int SM = ((n-1)*n)>>1;
        bool t = 0;
        dp[t][0] = 1;
        for(int i=2;i<=n;i++){
            for(int j=0;j<=SM;j++){
                dp[!t][j] = (dp[t][j+i-1]+dp[t][abs(j-i+1)])%MOD;
            }
            t=!t;
        }
        printf("%d\n",dp[t][S]);
    }
}