Submission #1258613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258613		biank	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	105 ms	95248 KiB

kangaroo

#include <bits/stdc++.h>

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

using namespace std;

using vi = vector<int>;

const int MAX_N = 2005;
const int MOD = 1000000007;

int memo1[MAX_N][MAX_N][2][2];
int memo2[MAX_N][MAX_N][2];

int dp(int n, int s, int t, bool inc) {
    if (s > t) return dp(n, n - s + 1, n - t + 1, !inc);
    if (n == 2) return inc;
    if (s > 1) {
        int &ret = memo1[n][s][inc][t == n];
        if (ret != -1) return ret;
        if (inc) {
            ret = dp(n, s - 1, t, inc) - dp(n - 1, s - 1, t - 1, !inc);
            if (ret < 0) ret += MOD;
        } else {
            ret = dp(n, s - 1, t, inc) + dp(n - 1, s - 1, t - 1, !inc);
            if (ret >= MOD) ret -= MOD;
        }
        return ret;
    }
    if (!inc) return 0;
    int &ret = memo2[n][t][inc];
    if (ret != -1) return ret;
    if (t < n) {
        ret = dp(n, n - t + 1, n, true) + dp(n, n - t + 1, n, false);
        if (ret >= MOD) ret -= MOD;
        return ret;
    }
    ret = 0;
    forsn(i, 2, n - 1) {
        ret += dp(n - 1, i, t - 1, false);
        if (ret >= MOD) ret -= MOD;
    }
    return ret;
}

int main() {
    
    int n, s, t;
    cin >> n >> s >> t;
    memset(memo1, -1, sizeof memo1);
    memset(memo2, -1, sizeof memo2);
    int ret = dp(n, s, t, false) + dp(n, s, t, true);
    if (ret >= MOD) ret -= MOD;
    cout << ret << '\n';
    
    return 0;
}    

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