Submission #1129705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129705		hamzahasa067	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	34 ms	32072 KiB

kangaroo

// يارب الخلاص عشان خلاص 
#include<bits/stdc++.h>

using namespace std;


#define int long long

const int MOD = 1e9  +7;

int add(int a,int b) {
  return (a+b) % MOD;
}
int mul(int a,int b) {
  return (a*b) % MOD;
}

main() {

ios_base::sync_with_stdio(0), cin.tie(nullptr),cout.tie(nullptr);





  int n,cs,cf;
  
  cin >> n >> cs >> cf;
  
  vector<vector<int>> dp(n+10, vector<int>(n+10));
  
  dp[1][1] = 1;
  int cntFix = 0;
  for(int i = 1;i<=n;i++) {
    cntFix += i == cs;
    cntFix += i == cf;
    
    for(int j = 1;j<=i;j++) { 
        if(i+1 == cs or i+1 == cf) {
          dp[i+1][j+1] = add(dp[i+1][j+1],dp[i][j]); // creates new component where i+1 goes to the beginning
          dp[i+1][j] = add(dp[i+1][j],dp[i][j]); // at i+1 to the beginning of an already existing component
        } else {
          dp[i+1][j-1] = add(dp[i+1][j-1] , mul(j-1, dp[i][j])); // merge two components inserting i+1 at any beginning or at any end
          dp[i+1][j+1] = add(dp[i+1][j+1] , mul(j+1 - cntFix, dp[i][j])); // create new component using i+1 at any beginning or at any end, but with respect to the fixed starts and ends
        }
    }
  }
  
  cout << dp[n][1] ;
  
  return 0;

}

Compilation message (stderr)

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

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