Cod sursa(job #3220838)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 4 aprilie 2024 22:18:33
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 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 val;
    vector <int> v;
}D[2][70003];
int n,i,j,t,S,nr;
const int C=35000;
const int MOD=194767;
int main()
{
    fin>>n>>S;
    if(S>C||S<-C)
    {
        fout<<0;
        return 0;
    }
    D[t][C].val=1;
    D[t][C].v.push_back(0);
    for(i=2;i<=n;i++)
    {
        t=1-t;
        for(j=2*C;j>=0;j--)
            if(D[1-t][j].val)
            {
                for(auto l:D[1-t][j].v)
                {
                    if(j+l+1<=2*C)
                    {
                        D[t][j+l+1].val=(D[t][j+nr+1].val+D[1-t][j].val)%MOD;
                        D[t][j+l+1].v.push_back(l+1);
                    }
                    if(j+l-1>=0)
                    {
                        D[t][j+l-1].val=(D[t][j+nr-1].val+D[1-t][j].val)%MOD;
                        D[t][j+l-1].v.push_back(l-1);
                    }
                }
                D[1-t][j].val=0;
                D[1-t][j].v.clear();
                ///fout<<j<<" "<<i<<"\n";
            }
    }
    fout<<D[t][min(2*C,S+C)].val%MOD;
    return 0;
}