Submission #1289446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289446		namious	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	48 ms	69708 KiB

kangaroo

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

#define int long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0) ,cin.tie(0),cout.tie(0);

const int maxn = 2e3+3 , mod = 1e9+7 , inf = 1e9+9;

int n,s,e;
int dp[maxn][2][maxn];
int pd[maxn][2][maxn];
int cnt[maxn][2];

int32_t main(){
    fast_io

    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);

    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 = cnt[c+1][1], a1 = (dp[n-c-1][0][s] + dp[n-c-1][1][s] - cnt[c+1][0] + mod) % mod;
                cnt[c][0] = (cnt[c][0] + a0) % mod , cnt[c][1] = (cnt[c][1] + a1) % mod;
                pd[ne][0][c] = a0 , pd[ne][1][c] = a1;
            } else {
                int a0 = cnt[c+1][1], a1 = (dp[n-c-1][0][s] + dp[n-c-1][1][s] - cnt[c+1][0] + mod) % mod;
                cnt[c][0] = (cnt[c][0] + a0) % mod , cnt[c][1] = (cnt[c][1] + a1) % mod;
                pd[ne][0][c] = a0 , pd[ne][1][c] = a1;
            }   
        }
    }

    cout << (pd[e][0][0] + pd[e][1][0]) % mod << endl;
}

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