Submission #569592

#	Time	Username	Problem	Language	Result	Execution time	Memory
569592		Abrar_Al_Samit	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	14 ms	31772 KiB

kangaroo

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

const int MX = 2005;
const int Mod = 1e9 + 7;

int add(int a, int b) {
  a += b;
  if(a>=Mod) a -= Mod;
  return a;
}
int mul(int a, int b) {
  return (a * 1LL * b) % Mod;
}
int n, cs, cf;
int dp[MX][MX/2][2][2];

int solve(int i, int j, bool ad1, bool ad2) {
  if(i==n-1) return 1;
  int &ret = dp[i][j][ad1][ad2];
  if(ret!=-1) return ret;
  if(i==cs || i==cf) return ret = solve(i+1, j, ad1, ad2);
  ret = 0;
  //new component
  if(j+1<(n+1)/2) ret = add(ret, solve(i+1, j+1, ad1, ad2));
  //merge
  if(j>2) ret = add(ret, mul(j-1, solve(i+1, j-1, ad1, ad2)));

  //extend
  if(!ad1 && i<cs) ret = add(ret, solve(i+1, j, 1, ad2));
  if(!ad2 && i<cf) ret = add(ret, solve(i+1, j, ad1, 1));

  return ret;
}
void PlayGround() {
  cin>>n>>cs>>cf;
  memset(dp, -1, sizeof dp);
  cout<<solve(1, 2, 0, 0)<<'\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  PlayGround();
  return 0;
}

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