Submission #1363882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363882		altern23	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	46 ms	55072 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 2000;
const int MOD = 1e9+7;

ll dp[MAXN+5][MAXN+5][3];

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;
      // cin >> tc;
      while (tc--) {
            ll N, S, T; cin >> N >> S >> T;

            dp[0][0][0] = 1;

            for (int i = 1; i <= N; i++) {
                  for (int j = 1; j <= i; j++) {
                        for (int k = 0; k <= 2; k++) {
                              bool z = (i == S || i == T);
                              if (k-z >= 0) {
                                    // make new cc
                                    dp[i][j][k] += dp[i-1][j-1][k-z]*(z ? 1LL : j-(k-z))%MOD;
                                    dp[i][j][k] %= MOD;
                                    if (!z) {
                                          // gabung 2 cc
                                          dp[i][j][k] += dp[i-1][j+1][k-z]*j%MOD;
                                          dp[i][j][k] %= MOD;
                                    }
                                    // tambah di ujung, tp ga nambah cc
                                    if (z) {
                                          dp[i][j][k] += dp[i-1][j][k-z]%MOD;
                                          dp[i][j][k] %= MOD;
                                    }                                    
                              }
                        }
                  }
            }
                  
            cout << dp[N][1][2] << "\n";
      }
}

/*

*/

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