Submission #314364

#	Time	Username	Problem	Language	Result	Execution time	Memory
314364		ivan_tudor	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	22 ms	14080 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
const int MOD=1000000007;
int dp[N][N];
inline void trans(long long val,int id,int col){
  if(col<0)
    return;
  val%=MOD;
  dp[id][col]+=val;
  if(dp[id][col]>MOD)
    dp[id][col]-=MOD;
}
int main()
{
  int n,cs,cf;
  scanf("%d%d%d",&n,&cs,&cf);
  if(cf<cs)
    swap(cf,cs);
  dp[1][0]=1;
  for(int i=1;i<cs;i++){
    for(int j=0;j<i;j++){
      trans(dp[i][j],i+1,j+1);
      trans(1LL*dp[i][j]*(j-1)*j,i+1,j-1);
    }
  }
  for(int j=0;j<cs;j++){
    trans(dp[cs][j],cs+1,j);
    trans(1LL*dp[cs][j]*j,cs+1,j-1);
  }
  for(int i=cs+1;i<cf;i++){
    for(int j=0;j<i;j++){
      trans(dp[i][j],i+1,j+1);
      trans(1LL*dp[i][j]*(j)*j,i+1,j-1);
    }
  }
  for(int j=0;j<cf;j++){
    trans(dp[cf][j],cf+1,j);
    trans(1LL*dp[cf][j]*j,cf+1,j-1);
  }
  for(int i=cf+1;i<=n;i++){
    for(int j=0;j<i;j++){
      trans(dp[i][j],i+1,j+1);
      trans(1LL*dp[i][j]*(j+1)*j,i+1,j-1);
    }
  }
  printf("%d",dp[n][0]);
  return 0;
}

Compilation message (stderr)

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

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