Submission #873687

#	Time	Username	Problem	Language	Result	Execution time	Memory
873687		maxFedorchuk	Kangaroo (CEOI16_kangaroo)	C++14	36 / 100	2 ms	2508 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

const long long MX=2e3+10;
const long long MOD=1e9+7;
long long mas[MX][MX][4]={0};

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    long long n,s,f;
    cin>>n>>s>>f;

    mas[1][1][0]=1;

    for(long long i=1;i<n;i++)
    {
        for(long long k=1;k<n;k++)
        {
            if((i+1)<=s)
            {
                mas[i+1][k][2]=(mas[i+1][k][2]+mas[i][k][0])%MOD;
                mas[i+1][k][3]=(mas[i+1][k][1]+mas[i][k][1])%MOD;
            }

            if((i+1)<=f)
            {
                mas[i+1][k][1]=(mas[i+1][k][1]+mas[i][k][0])%MOD;
                mas[i+1][k][3]=(mas[i+1][k][3]+mas[i][k][2])%MOD;
            }


            if((i+1)!=s && (i+1)!=f)
            {
                mas[i+1][k-1][0]=(mas[i+1][k-1][0]+mas[i][k][0]*(k-1))%MOD;
                mas[i+1][k-1][1]=(mas[i+1][k-1][1]+mas[i][k][1]*(k-1))%MOD;
                mas[i+1][k-1][2]=(mas[i+1][k-1][2]+mas[i][k][2]*(k-1))%MOD;
                mas[i+1][k-1][3]=(mas[i+1][k-1][3]+mas[i][k][3]*(k-1))%MOD;
            }

            if((i+1)==s)
            {
                mas[i+1][k+1][0]=(mas[i+1][k+1][0]+mas[i][k][0])%MOD;
                mas[i+1][k+1][1]=(mas[i+1][k+1][1]+mas[i][k][1])%MOD;
            }

            if((i+1)==f)
            {
                mas[i+1][k+1][0]=(mas[i+1][k+1][0]+mas[i][k][0])%MOD;
                mas[i+1][k+1][2]=(mas[i+1][k+1][2]+mas[i][k][2])%MOD;
            }


            if((i+1)<s && (i+1)<f)
            {
                mas[i+1][k+1][0]=(mas[i+1][k+1][0]+mas[i][k][0]*(k+1))%MOD;
                mas[i+1][k+1][1]=(mas[i+1][k+1][1]+mas[i][k][1]*(k))%MOD;
                mas[i+1][k+1][2]=(mas[i+1][k+1][2]+mas[i][k][2]*(k))%MOD;
                mas[i+1][k+1][3]=(mas[i+1][k+1][3]+mas[i][k][3]*(k-1))%MOD;
                continue;
            }

            if((i+1)>s && (i+1)<f)
            {
                mas[i+1][k+1][0]=(mas[i+1][k+1][0]+mas[i][k][0]*(k))%MOD;
                mas[i+1][k+1][1]=(mas[i+1][k+1][1]+mas[i][k][1]*(k-1))%MOD;
                mas[i+1][k+1][2]=(mas[i+1][k+1][2]+mas[i][k][2]*(k))%MOD;
                mas[i+1][k+1][3]=(mas[i+1][k+1][3]+mas[i][k][3]*(k-1))%MOD;
                continue;
            }

            if((i+1)<s && (i+1)>f)
            {
                mas[i+1][k+1][0]=(mas[i+1][k+1][0]+mas[i][k][0]*(k))%MOD;
                mas[i+1][k+1][1]=(mas[i+1][k+1][1]+mas[i][k][1]*(k))%MOD;
                mas[i+1][k+1][2]=(mas[i+1][k+1][2]+mas[i][k][2]*(k-1))%MOD;
                mas[i+1][k+1][3]=(mas[i+1][k+1][3]+mas[i][k][3]*(k-1))%MOD;
                continue;
            }

            if((i+1)>s && (i+1)>f)
            {
                mas[i+1][k+1][0]=(mas[i+1][k+1][0]+mas[i][k][0]*(k-1))%MOD;
                mas[i+1][k+1][1]=(mas[i+1][k+1][1]+mas[i][k][1]*(k-1))%MOD;
                mas[i+1][k+1][2]=(mas[i+1][k+1][2]+mas[i][k][2]*(k-1))%MOD;
                mas[i+1][k+1][3]=(mas[i+1][k+1][3]+mas[i][k][3]*(k-1))%MOD;
                continue;
            }
        }
    }

    cout<<(mas[n][1][0]+mas[n][1][1]+mas[n][1][2]+mas[n][1][3])%MOD<<"\n";
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49