Submission #1118234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118234		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	1 ms	336 KiB

kangaroo

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define _FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl "\n"

const int MOD = 1e9 + 7;

ifstream inFile("kangaroo.in");
ofstream outFile("kangaroo.out");

void solve() {
    int n,cs,cf; inFile>>n>>cs>>cf;

    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    vector<vector<int>> prefixSum(n+1, vector<int>(n+1, 0));

    dp[1][cs] = 1;
    for (int i=1; i<=n; i++) prefixSum[1][i] = (prefixSum[1][i-1] + dp[1][i]) % MOD;

    for (int i=2; i<=n; i++) { 
        for (int j=1; j<=n; j++) {
            if (j > 1) {
                dp[i][j] += prefixSum[i - 1][j - 1];
                dp[i][j] %= MOD;
            }
            if (j < n) {
                dp[i][j] += (prefixSum[i - 1][n] - prefixSum[i - 1][j] + MOD) % MOD;
                dp[i][j] %= MOD;
            }
        }
        for (int j=1; j<=n; j++)  prefixSum[i][j] = (prefixSum[i][j-1]+dp[i][j])%MOD;
    }
    outFile<<dp[n][cf];
}

signed main() {
    //_FastIO;
    int t=1;
    //cin>>t;
    while (t--) solve();
    return 0;
}

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