Submission #1349850

#TimeUsernameProblemLanguageResultExecution timeMemory
1349850SSKMFKangaroo (CEOI16_kangaroo)C++20
51 / 100
494 ms40908 KiB
#include <bits/stdc++.h>
using namespace std;

const int mod(1000000007);
int modalitati[201][201][201][2];
bool vizitat[201][201][201][2];

int Get (int lungime , int inceput , int sfarsit , int directie)
{
    if (vizitat[lungime][inceput][sfarsit][directie])
        { return modalitati[lungime][inceput][sfarsit][directie]; }

    vizitat[lungime][inceput][sfarsit][directie] = true;
    if (lungime == 2) {
        if (directie == 0) { modalitati[lungime][inceput][sfarsit][0] = (inceput < sfarsit ? 1 : 0); }
        else { modalitati[lungime][inceput][sfarsit][1] = (inceput < sfarsit ? 0 : 1); }
        return modalitati[lungime][inceput][sfarsit][directie];
    }

    if (directie == 0)
    {
        for (int indice = inceput + 1 ; indice <= lungime ; indice++) {
            if (indice != sfarsit)
                { (modalitati[lungime][inceput][sfarsit][directie] += Get(lungime - 1 , indice - 1 , sfarsit - (inceput < sfarsit ? 1 : 0) , 1)) %= mod; }
        }
    }
    else
    {
        for (int indice = inceput - 1 ; indice ; indice--) {
            if (indice != sfarsit)
                { (modalitati[lungime][inceput][sfarsit][directie] += Get(lungime - 1 , indice , sfarsit - (inceput < sfarsit ? 1 : 0) , 0)) %= mod; }
        }
    }

    return modalitati[lungime][inceput][sfarsit][directie];
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime , inceput , sfarsit;
    cin >> lungime >> inceput >> sfarsit;
    cout << (Get(lungime , inceput , sfarsit , 0) + Get(lungime , inceput , sfarsit , 1)) % mod;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...