Cod sursa(job #2156131)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 8 martie 2018 15:04:36
Problema 1-sir Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<cstdio>
#define mod 194767
int dp[2][66005];
int main(){
freopen("1-sir.in","r",stdin);
freopen("1-sir.out","w",stdout);
int n,s,i,j;
scanf("%d%d",&n,&s);
n--;
if (n*(n+1)/2<s || n*(n+1)/2*(-1)>s){
printf("0\n");
return 0;}
s=s+33000;
int lim=n*(n+1)/2+33000,lim2=n*(n+1)/2*(-1)+33000;
dp[0][33000]=1;
for(i=1;i<=n;i++){
int nr=i%2;
for(j=lim2;j<=lim;j++){
dp[nr][j]=0;
if (j-(n-i+1)>=lim2)
dp[nr][j]=dp[nr][j]+dp[1-nr][j-(n-i+1)];
if (j+(n-i+1)<=lim)
dp[nr][j]=dp[nr][j]+dp[1-nr][j+(n-i+1)];
if (dp[nr][j]>=mod)
dp[nr][j]-=mod;}}
printf("%d\n",dp[n%2][s]);
return 0;}