Submission #959313

#	Time	Username	Problem	Language	Result	Execution time	Memory
959313		caterpillow	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	26 ms	31916 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;

const ll MOD = 1e9 + 7;

void add(ll& a, ll b) {
    a = (a + (b % MOD)) % MOD;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, st, en; cin >> n >> st >> en;
    vt dp(n + 1, vt<ll>(n + 2));
    dp[1][1] = 1;
    FOR (i, 2, n + 1) {
        FOR (j, 1, n + 1) {
            if (i == st || i == en) { // place either as a new component, or glue to some previous one
                add(dp[i][j], dp[i - 1][j - 1] + dp[i - 1][j]);
            } else { // place either as a new component, or glue together two previous ones
                add(dp[i][j], dp[i - 1][j - 1] * (j - (i > st) - (i > en)) + dp[i - 1][j + 1] * j);
            }
        }
    }
    cout << dp[n][1] << endl;
}

Compilation message (stderr)

kangaroo.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

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