Cod sursa(job #3220863)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 5 aprilie 2024 09:08:08
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 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;
    int v[3];
}D[2][66003];
int n,i,j,t,S,nr1,nr2;
const int C=25000;
const int MOD=194767;
int main()
{
    fin>>n>>S;
    D[t][C]={1,0};
    D[t][C].v[0]=0;
    for(i=2;i<=n;i++)
    {
        t=1-t;
        for(j=2*C;j>=0;j--)
            if(D[1-t][j].p)
            {
                nr1=D[1-t][j].v[1];
                nr2=D[1-t][j].v[2];
                if(j+nr1+1<=2*C)
                {
                    D[t][j+nr1+1].p=(D[t][j+nr1+1].p+D[1-t][j].p)%MOD;
                    D[t][j+nr1+1].v[++D[t][j+nr1+1].v[0]]=nr1+1;
                }
                if(D[1-t][j].v[0]>1&&j+nr2+1<=2*C)
                {
                    D[t][j+nr2+1].p=(D[t][j+nr2+1].p+D[1-t][j].p)%MOD;
                    D[t][j+nr2+1].v[++D[t][j+nr2+1].v[0]]=nr2+1;
                }
                if(j+nr1-1>=0)
                {
                    D[t][j+nr1-1].p=(D[t][j+nr1-1].p+D[1-t][j].p)%MOD;
                    D[t][j+nr1-1].v[++D[t][j+nr1-1].v[0]]=nr1-1;
                }
                if(D[1-t][j].v[0]>1&&j+nr2-1>=0)
                {
                    D[t][j+nr2-1].p=(D[t][j+nr2-1].p+D[1-t][j].p)%MOD;
                    D[t][j+nr2-1].v[++D[t][j+nr2-1].v[0]]=nr2-1;
                }
                D[1-t][j]={0,0};
                D[1-t][j].v[0]=0;
                ///fout<<j<<" "<<i<<"\n";
            }
    }
    fout<<D[t][min(2*C,S+C)].p%MOD;
    return 0;
}