Cod sursa(job #3220795)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 4 aprilie 2024 20:47:09
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <climits>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
ifstream fin ("1-sir.in");
ofstream fout("1-sir.out");
struct elem
{
    int p,val;
}D[2][66000];
int n,i,j,t,S,nr;
const int C=33000;
const int MOD=194767;
int main()
{
    fin>>n>>S;
    D[t][C]={1,0};
    for(i=2;i<=n;i++)
    {
        t=1-t;
        for(j=0;j<=S+C;j++)
            D[t][j]=D[1-t][j];
        for(j=S+C;j>=0;j--)
            if(D[1-t][j].p)
            {
                nr=D[1-t][j].val;
                if(j+nr+1<=S+C)
                    D[t][j+nr+1]={(D[t][j+nr+1].p+D[1-t][j].p)%MOD,nr+1};
                if(j+nr-1>=0)
                    D[t][j+nr-1]={(D[t][j+nr-1].p+D[1-t][j].p)%MOD,nr-1};
                D[t][j]={0,0};
            }
    }
    fout<<D[t][S+C].p%MOD;
    return 0;
}