Submission #1187652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187652		peteza	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	24 ms	15944 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;

int n, sf, st, psd;
int dp[2005][2005]; //filled 1-i with j components

int main() {
    psd = 0;
    cin >> n >> sf >> st;
    dp[0][0] = 1;
    for(int i=1;i<=n;i++) {
        if(i == sf || i == st) {
            for(int k=1;k<=n;k++) dp[i][k] = dp[i-1][k];
            for(int k=0;k<=n;k++) {
                dp[i][k+1] += dp[i-1][k];
                if(dp[i][k+1] >= mod) dp[i][k+1] -= mod;
            }
            psd++;
        } else {
            for(int k=0;k<=n;k++) { //make new compo
                dp[i][k+1] += 1ll * dp[i-1][k] * max(0, k+1 - psd) % mod;
                if(dp[i][k+1] >= mod) dp[i][k+1] -= mod;
            }
            for(int k=2;k<=n;k++) { //merge existing compo
                dp[i][k-1] += 1ll * dp[i-1][k] * (k-1) % mod;
                if(dp[i][k-1] >= mod) dp[i][k-1] -= mod;
            }
        }
    }
    cout << dp[n][1];
}

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