Submission #1180880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180880		candi_ositos	Kangaroo (CEOI16_kangaroo)	C++20	0 / 100	0 ms	324 KiB

kangaroo

#include <bits/stdc++.h>
#define MD 1000000007
using namespace std;
void solve();
int f(int i, int j, int k);
int g(int i, int j, int k);
map <pair <pair <int, int>, int>, int> df;
map <pair <pair <int, int>, int>, int> dg;
int main()
{
    int T=1;
  //  cin>>T;
    for(int i=1; i<T; ++i)
    {
        solve();
        cout<<"\n";
    }
    if(T)
    {
        solve();
    }
    return 0;
}
void solve()
{
    int N, cs, cf;
    cin>>N>>cs>>cf;
    cout<<f(cs-1, cf-cs-1, N-cf)+g(cs-1, cf-cs-1, N-cf);
    return;
}
int f(int i, int j, int k)
{
    pair <pair <int, int>, int> aguss=make_pair(make_pair(i, j), k);
    if(df.count(aguss))
    {
        return df[aguss];
    }
    if(i==0 && j==0 && k==0)
    {
        df[aguss]=1;
        return 1;
    }
    int nw=0;
    for(int l=0; l<j; ++l)
    {
        nw+=g(i+l, j-l-i, k);
        if(nw>=MD)
        {
            nw=nw-MD;
        }
    }
    for(int l=0; l<k; ++l)
    {
        nw+=f(l, k-l-1, i+j);
        if(nw>=MD)
        {
            nw=nw-MD;
        }
    }
    df[aguss]=nw;
    return nw;
}
int g(int i, int j, int k)
{
    pair <pair <int, int>, int> aguss=make_pair(make_pair(i, j), k);
    if(dg.count(aguss))
    {
        return dg[aguss];
    }
    int nw=0;
    for(int l=0; l<i; ++l)
    {
        nw+=f(i-l-1, j+l, k);
        if(nw>=MD)
        {
            nw=nw-MD;
        }
    }
    dg[aguss]=nw;
    return nw;
}

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