Submission #127640

#	Time	Username	Problem	Language	Result	Execution time	Memory
127640		Abelyan	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	7 ms	504 KiB

kangaroo

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x);
#define dbgv(v);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=2e3+10;
const ll MOD=1e9+7;

ll x[N][N],dp[N][N],suf[N][N];

int main(){
    fastio;
    srng;
    int n,s,f;
    cin>>n>>s>>f;
    assert(n<=10);
    if (s>f)swap(s,f);
    dp[1][0]=1;
    suf[1][0]=1;
    FORT(i,2,n){
        FOR(j,i-1){
            dp[i][j]=suf[i-1][i-j-2];
            //cout<<dp[i][j]<<" ";
        }
        dp[i][i-1]=dp[i][i-2];
        //cout<<endl;
        FORD(j,i){
            suf[i][j]=suf[i][j+1]+dp[i][j];
            suf[i][j]%=MOD;
        }
    }
    FORT(i,1,n){
        int k=i-(n-f);
        if (k<=1)continue;
        i--;
        k--;
        if (i==1 &&k==1){
            x[i+1][1]=1;
        }
        if (k!=1 && i%2)
            x[i+1][1]=dp[i-1][k-2];
        if (i%2==0){
            if (k==i)x[i+1][1]+=dp[i-2][0];
            else x[i+1][1]+=dp[i-1][i-k-1];
        }
        i++;
        x[i][1]%=MOD;
        //cout<<x[i][1]<<" ";
    }
    //cout<<endl;
    FORT(i,1,n){
        int k=i-(n-s);
        if (k<=1)continue;
        x[i][2]=x[i][1]+x[i-1][1];
        x[i][2]%=MOD;
        //cout<<x[i][2]<<" ";
    }
    //cout<<endl;
    FORT(i,3,n){
        FORT(j,3,n){
            x[n][i]=(2*x[n][i-1]-x[n][i-2]-x[n-2][i-2]+2*MOD)%MOD;
        }
    }
    cout<<x[n][s]<<endl;
}

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