Submission #1289081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289081		djawadmain	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	36 ms	44840 KiB

kangaroo

#include<iostream>
#include<vector>

using namespace std;

#define ll long long
#define ld long double
#define pii pair<ll, ll>
#define RUN_LIKE_DJAWAD (ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0));
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define maxn 2001

const int mod = 1e9 + 7;

int dp[maxn][2][maxn];

int n, s, e;

int pd[maxn][2][maxn];

int smp[maxn][2];

int main(){

    RUN_LIKE_DJAWAD

    dp[1][0][1] = 1, dp[1][1][1];

    for (int i = 2; i < maxn; i++){

        int sm = 0;

        for (int j = i - 1; j > 0; j--){

            sm = (sm + dp[i - 1][1][j]) % mod;
            dp[i][0][j] = sm;
        }

        sm = 0;

        for (int j = 2; j <= i; j++){

            sm = (sm + dp[i - 1][0][j - 1]) % mod;
            dp[i][1][j] = sm;
        }
    }

    cin >> n >> s >> e;

    if (e < s) swap(s, e);

    int cc = e - 1;
    int d = n - e;

    for (int ne = n; ne >= e; ne--){

        for (int c = 0; c <= ne - e; c++){

            bool bt = (n - c - 1) & 1;

            if (bt){

                int a0 = smp[c + 1][1], a1 = (dp[n - c - 1][0][s] + dp[n - c - 1][1][s] - smp[c + 1][0] + mod) % mod;

                smp[c][0] = (smp[c][0] + a0) % mod;
                smp[c][1] = (smp[c][1] + a1) % mod;

                pd[ne][0][c] = a0;
                pd[ne][1][c] = a1;

            } else {

                int a0 = smp[c + 1][1], a1 = (dp[n - c - 1][0][s] + dp[n - c - 1][1][s] - smp[c + 1][0] + mod) % mod;

                smp[c][0] = (smp[c][0] + a0) % mod;
                smp[c][1] = (smp[c][1] + a1) % mod;

                pd[ne][0][c] = a0;
                pd[ne][1][c] = a1;
            }   
        }
    }

    cout << (pd[e][0][0] + pd[e][1][0]) % mod << "\n";
}

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