oj.uz

Submission #57182

# Submission time Handle Problem Language Result Execution time Memory
57182 2018-07-14T08:38:44 Z ruhanhabib39 Kangaroo (CEOI16_kangaroo) C++17
51 / 100
 377 ms 290804 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long Long;

const Long MOD = 1000000007;

int N, cs, cf;
Long dp[2][200 + 10][200 + 10][200 + 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][lp] != -1) 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);
   memset(dp, -1, sizeof(dp));
   printf("%lld\n", (f(0,cs-1,N-cs,cf-1) + f(1,cs-1,N-cs,cf-1)) % MOD);
}

Compilation message

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 145272 KB Output is correct
2 Correct 123 ms 145572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 145272 KB Output is correct
2 Correct 123 ms 145572 KB Output is correct
3 Correct 113 ms 145572 KB Output is correct
4 Correct 115 ms 145572 KB Output is correct
5 Correct 121 ms 145704 KB Output is correct
6 Correct 107 ms 145704 KB Output is correct
7 Correct 104 ms 145704 KB Output is correct
8 Correct 117 ms 145704 KB Output is correct
9 Correct 126 ms 145920 KB Output is correct
10 Correct 125 ms 145920 KB Output is correct
11 Correct 103 ms 145920 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 145272 KB Output is correct
2 Correct 123 ms 145572 KB Output is correct
3 Correct 113 ms 145572 KB Output is correct
4 Correct 115 ms 145572 KB Output is correct
5 Correct 121 ms 145704 KB Output is correct
6 Correct 107 ms 145704 KB Output is correct
7 Correct 104 ms 145704 KB Output is correct
8 Correct 117 ms 145704 KB Output is correct
9 Correct 126 ms 145920 KB Output is correct
10 Correct 125 ms 145920 KB Output is correct
11 Correct 103 ms 145920 KB Output is correct
12 Correct 223 ms 147480 KB Output is correct
13 Correct 186 ms 147480 KB Output is correct
14 Correct 109 ms 147480 KB Output is correct
15 Correct 192 ms 147480 KB Output is correct
16 Correct 201 ms 147480 KB Output is correct
17 Correct 205 ms 147480 KB Output is correct
18 Correct 135 ms 147480 KB Output is correct
19 Correct 201 ms 147480 KB Output is correct
20 Correct 262 ms 147480 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 145272 KB Output is correct
2 Correct 123 ms 145572 KB Output is correct
3 Correct 113 ms 145572 KB Output is correct
4 Correct 115 ms 145572 KB Output is correct
5 Correct 121 ms 145704 KB Output is correct
6 Correct 107 ms 145704 KB Output is correct
7 Correct 104 ms 145704 KB Output is correct
8 Correct 117 ms 145704 KB Output is correct
9 Correct 126 ms 145920 KB Output is correct
10 Correct 125 ms 145920 KB Output is correct
11 Correct 103 ms 145920 KB Output is correct
12 Correct 223 ms 147480 KB Output is correct
13 Correct 186 ms 147480 KB Output is correct
14 Correct 109 ms 147480 KB Output is correct
15 Correct 192 ms 147480 KB Output is correct
16 Correct 201 ms 147480 KB Output is correct
17 Correct 205 ms 147480 KB Output is correct
18 Correct 135 ms 147480 KB Output is correct
19 Correct 201 ms 147480 KB Output is correct
20 Correct 262 ms 147480 KB Output is correct
21 Runtime error 377 ms 290804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -