# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
127625 | 2019-07-09T17:29:29 Z | TadijaSebez | Kangaroo (CEOI16_kangaroo) | C++11 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int mod=1e9+7; const int N=2005; int dp[N][N][2],sum[N][N][2]; int Get(int i, int l, int r, int t) { int x=sum[i][r][t]-sum[i][l-1][t]; if(x<0) x+=mod; return x; } int main() { int n,cs,cf; scanf("%i %i %i",&n,&cs,&cf); dp[1][1][0]=dp[1][1][1]=1; for(int l=2;l<=n;l++) { for(int i=1;i<=l-1;i++) for(int j=1;j<=l-1;j++) { sum[i][j][0]=sum[i][j-1][0]+dp[i][j][0]; if(sum[i][j][0]>=mod) sum[i][j][0]-=mod; sum[i][j][1]=sum[i][j-1][1]+dp[i][j][1]; if(sum[i][j][1]>=mod) sum[i][j][1]-=mod; } for(int i=1;i<=l;i++) for(int j=1;j<=l;j++) { if(i!=j) { dp[i][j][0]=Get(i-(i>j),1,j-1,1); dp[i][j][1]=Get(i-(i>j),j,l-1,0); } else dp[i][j][0]=dp[i][j][1]=0; } } int ans=add(dp[cs][cf][0],dp[cs][cf][1]); printf("%i\n",ans); return 0; }