Submission #670847

#	Time	Username	Problem	Language	Result	Execution time	Memory
670847		Kahou	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	340 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
 
int mod = 1e9 + 7;
int add(int a, int b) {
    a += b;
    if (a < 0) a += mod;
    if (a >= mod) a -= mod;
    return a;
}
int mul(int a, int b) {
    return 1ll*a*b%mod;
}
 
const int N = 2050;
int n, cs, cf;
int dp[N][N], pd[N][N];
 
void solve() {
    cin >> n >> cs >> cf;
    if (cs > cf) swap(cs, cf);

    pd[2][2] = 1;
    for (int i = 3; i <= n; i++) {
            if (i&1) for (int j = 1; j <= i-1; j++) pd[i][1] = add(pd[i][1], pd[i-1][j]);
            for (int j = 2; j <= i; j++) {
                    pd[i][j] = add(pd[i][j-1], (i&1? -1:1)*pd[i-1][j-1]);
            }
            pd[i][1] = 0;
    }

    for (int i = 2; i <= n; i++) {
            if (i > n-cf) dp[i][1] = pd[i][i-n+cf];
            dp[i][2] = add(dp[i][1], dp[i-1][1]);
            for (int j = 3; j <= i; j++) {
                dp[i][j] = add(add(dp[i][j-1], dp[i][j-1]), add(dp[i][j-2], -dp[i-2][j-2]));
            }
    }
    cout << dp[n][cs] << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

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