# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
49344 | 2018-05-26T09:32:17 Z | 3zp | Kangaroo (CEOI16_kangaroo) | C++14 | 3 ms | 1152 KB |
#include<bits/stdc++.h> using namespace std; int dp[2][2009][2009][3]; int prefdp[2][2009][2009][3]; int mod = 1e9+ 7; main(){ int n,l,r; cin >> n >> l >> r; dp[1][1][1][1] = 1; dp[1][1][1][0] = 1; prefdp[1][1][1][1] = 1; prefdp[1][1][1][0] = 1; for(int N = 2; N <= n; N++){ int n0 = N % 2, n1 = 1 - n0; for(int L = 1; L <= n; L++){ for(int R = max(0,r - (n- N)); R <= r; R++){ for(int D = 0; D < 2; D++){ if(L != R){ int nR = R; if (R > L) nR--; if(D == 0){ dp[n0][L][R][D] += prefdp[n1][N-1][nR][1-D] - prefdp[n1][L-1][nR][1-D] + mod; while (dp[n0][L][R][D] >= mod) dp[n0][L][R][D]-=mod; } else { dp[n0][L][R][D] += prefdp[n1][L-1][nR][1-D]; while (dp[n0][L][R][D] >= mod) dp[n0][L][R][D]-=mod; } } prefdp[n0][L][R][D] = prefdp[n0][L-1][R][D] + dp[n0][L][R][D]; if( prefdp[n0][L][R][D] >= mod) prefdp[n0][L][R][D] -= mod; } } } } cout << (dp[n%2][l][r][0] + dp[n%2][l][r][1]) % mod << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 488 KB | Output is correct |
3 | Correct | 2 ms | 952 KB | Output is correct |
4 | Incorrect | 3 ms | 1152 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 488 KB | Output is correct |
3 | Correct | 2 ms | 952 KB | Output is correct |
4 | Incorrect | 3 ms | 1152 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 488 KB | Output is correct |
3 | Correct | 2 ms | 952 KB | Output is correct |
4 | Incorrect | 3 ms | 1152 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |