Submission #136163

#	Time	Username	Problem	Language	Result	Execution time	Memory
136163		dragonslayerit	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	39 ms	15996 KiB

kangaroo

#include <cstdio>

const int MOD=1e9+7;

int dp[2001][2001];//index,#ccs

void addmod(int& x,long long y){
  x=(x+y)%MOD;
}

int main(){
  int N,S,T;
  scanf("%d %d %d",&N,&S,&T);
  S--,T--;
  dp[0][0]=1;
  for(int i=0;i<N;i++){
    if(i==S||i==T){
      for(int cc=0;cc<N;cc++){
	if(cc) addmod(dp[i+1][cc],dp[i][cc]);
	addmod(dp[i+1][cc+1],dp[i][cc]);
      }
    }else{
      for(int cc=0;cc<N;cc++){
	addmod(dp[i+1][cc+1],dp[i][cc]*1LL*(cc+1-(i>S)-(i>T)));
	if(cc>0) addmod(dp[i+1][cc-1],dp[i][cc]*1LL*(cc-1));
      }
    }
  }
  printf("%d\n",dp[N][1]);
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&N,&S,&T);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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