Submission #35809

#	Time	Username	Problem	Language	Result	Execution time	Memory
35809		DoanPhuDuc	Kangaroo (CEOI16_kangaroo)	C++98	100 / 100	136 ms	65204 KiB

kangaroo

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;

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

int n, s, t;
int dp[N][N][2][2];

void Update(int &a, int b) {
    a += b; if (a >= BASE) a -= BASE;
}

LL P2(LL n) {
    return n * (n - 1) % BASE;
}

int Compute(int i, int j, int L, int R) {
    if (j < 0) return 0;
    if (i == n) return (j == 0) ? 1 : 0;
    int &ans = dp[i][j][L][R];
    if (ans != -1) return ans;
    ans = 0;
    if (i == s) {
        Update(ans, Compute(i + 1, j, 1, R));
        Update(ans, (LL)j * Compute(i + 1, j - 1, 1, R) % BASE);
    } else if (i == t) {
        Update(ans, Compute(i + 1, j, L, 1));
        Update(ans, (LL)j * Compute(i + 1, j - 1, L, 1) % BASE);
    } else {
        Update(ans, Compute(i + 1, j + 1, L, R));
        if (L == 1) Update(ans, (LL)j * Compute(i + 1, j - 1, L, R) % BASE);
        if (R == 1) Update(ans, (LL)j * Compute(i + 1, j - 1, L, R) % BASE);
        Update(ans, P2(j) * Compute(i + 1, j - 1, L, R) % BASE);
    }
    return ans;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d%d", &n, &s, &t);
    memset(dp, -1, sizeof dp);
    printf("%d", Compute(1, 0, 0, 0));
    return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:54:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &s, &t);
                                ^

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