Submission #57233

#	Time	Username	Problem	Language	Result	Execution time	Memory
57233		ruhanhabib39	Kangaroo (CEOI16_kangaroo)	C++17	36 / 100	2056 ms	504464 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
 
typedef long long Long;
 
const Long MOD = 1000000007;
 
int N, cs, cf;
map<int,Long> dp[2][2000 + 10][2000 + 10];
 
Long f(int di, int l, int r, int lp) {
   if(l < 0 || r < 0 || l >= N || r >= N) return 0;
   if(dp[di][l][r].count(lp)) return dp[di][l][r][lp];
   if(l+r == 1) {
      return dp[di][l][r][lp] = (di && r) || (!di && l);
   }
   Long rs = 0;
   if(di) {
      rs = f(1,l+1,r-1,lp);
      if(l+1 != lp) rs += f(0, l, r-1, lp < l+1 ? lp : lp - 1);
   } else {
      rs = f(0,l-1,r+1,lp);
      if(l != lp) rs += f(1, l-1, r, lp < l ? lp : lp - 1);
   }
   rs %= MOD;
   return dp[di][l][r][lp] = rs;
}
 
int main() {
   //freopen("kangaroo.in", "r", stdin);
   //freopen("kangaroo.out", "w", stdout);
   scanf("%d%d%d", &N, &cs, &cf);
   if(cs > cf) swap(cs, cf);
   printf("%lld\n", (f(0,cs-1,N-cs,cf-1) + f(1,cs-1,N-cs,cf-1)) % MOD);
}

Compilation message (stderr)

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

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