제출 #1258613

#제출 시각아이디문제언어결과실행 시간메모리
1258613biank캥거루 (CEOI16_kangaroo)C++20
100 / 100
105 ms95248 KiB
#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;
}    

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...