# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52953 |
2018-06-27T08:40:54 Z |
강태규(#1381) |
Kangaroo (CEOI16_kangaroo) |
C++11 |
|
81 ms |
32204 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int u1[2001][2001];
int dp[2001][2001];
const int mod = 1e9 + 7;
int pro_u1(int n, int e) {
if (e <= 1) return 0;
if (n <= 2) return 1;
if (u1[n][e] != -1) return u1[n][e];
int ret = 0;
if (e == 2) {
if (n & 1) {
for (int i = 2; i < n; ++i) {
ret += pro_u1(n - 1, i);
ret %= mod;
}
}
else ret = 0;
}
else if (n & 1) {
ret += pro_u1(n, e - 1);
ret += mod - pro_u1(n - 1, e - 1);
ret %= mod;
}
else {
ret += pro_u1(n, e - 1);
ret += pro_u1(n - 1, e - 1);
ret %= mod;
}
return u1[n][e] = ret;
}
int pro_dp(int n, int s, int e) {
if (dp[n][s] != -1) return dp[n][s];
int ret = 0;
if (s > 2) {
ret += (pro_dp(n, s - 1, e) << 1);
ret %= mod;
ret += mod - pro_dp(n, s - 2, e);
ret %= mod;
ret += mod - pro_dp(n - 2, s - 2, e - 2);
ret %= mod;
}
else if (s == 2) ret = (pro_u1(n - 1, e - 1) + pro_u1(n, e)) % mod;
else if (s == 1) ret = pro_u1(n, e);
return dp[n][s] = ret;
}
int main() {
for (int i = 0; i <= 2000; ++i) {
for (int j = 0; j <= 2000; ++j) {
dp[i][j] = -1;
u1[i][j] = -1;
}
}
int n, s, e;
scanf("%d%d%d", &n, &s, &e);
if (s > e) swap(s, e);
printf("%d\n", pro_dp(n, s, e));
return 0;
}
Compilation message
kangaroo.cpp: In function 'int main()':
kangaroo.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &s, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31608 KB |
Output is correct |
2 |
Correct |
32 ms |
31844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31608 KB |
Output is correct |
2 |
Correct |
32 ms |
31844 KB |
Output is correct |
3 |
Correct |
27 ms |
31844 KB |
Output is correct |
4 |
Correct |
28 ms |
31844 KB |
Output is correct |
5 |
Correct |
30 ms |
31844 KB |
Output is correct |
6 |
Correct |
32 ms |
31844 KB |
Output is correct |
7 |
Correct |
29 ms |
31844 KB |
Output is correct |
8 |
Correct |
31 ms |
31904 KB |
Output is correct |
9 |
Correct |
29 ms |
31904 KB |
Output is correct |
10 |
Correct |
27 ms |
31904 KB |
Output is correct |
11 |
Correct |
30 ms |
31904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31608 KB |
Output is correct |
2 |
Correct |
32 ms |
31844 KB |
Output is correct |
3 |
Correct |
27 ms |
31844 KB |
Output is correct |
4 |
Correct |
28 ms |
31844 KB |
Output is correct |
5 |
Correct |
30 ms |
31844 KB |
Output is correct |
6 |
Correct |
32 ms |
31844 KB |
Output is correct |
7 |
Correct |
29 ms |
31844 KB |
Output is correct |
8 |
Correct |
31 ms |
31904 KB |
Output is correct |
9 |
Correct |
29 ms |
31904 KB |
Output is correct |
10 |
Correct |
27 ms |
31904 KB |
Output is correct |
11 |
Correct |
30 ms |
31904 KB |
Output is correct |
12 |
Correct |
34 ms |
31904 KB |
Output is correct |
13 |
Correct |
30 ms |
31916 KB |
Output is correct |
14 |
Correct |
28 ms |
31952 KB |
Output is correct |
15 |
Correct |
27 ms |
31952 KB |
Output is correct |
16 |
Correct |
27 ms |
31952 KB |
Output is correct |
17 |
Correct |
28 ms |
31972 KB |
Output is correct |
18 |
Correct |
28 ms |
31972 KB |
Output is correct |
19 |
Correct |
29 ms |
31972 KB |
Output is correct |
20 |
Correct |
27 ms |
32008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31608 KB |
Output is correct |
2 |
Correct |
32 ms |
31844 KB |
Output is correct |
3 |
Correct |
27 ms |
31844 KB |
Output is correct |
4 |
Correct |
28 ms |
31844 KB |
Output is correct |
5 |
Correct |
30 ms |
31844 KB |
Output is correct |
6 |
Correct |
32 ms |
31844 KB |
Output is correct |
7 |
Correct |
29 ms |
31844 KB |
Output is correct |
8 |
Correct |
31 ms |
31904 KB |
Output is correct |
9 |
Correct |
29 ms |
31904 KB |
Output is correct |
10 |
Correct |
27 ms |
31904 KB |
Output is correct |
11 |
Correct |
30 ms |
31904 KB |
Output is correct |
12 |
Correct |
34 ms |
31904 KB |
Output is correct |
13 |
Correct |
30 ms |
31916 KB |
Output is correct |
14 |
Correct |
28 ms |
31952 KB |
Output is correct |
15 |
Correct |
27 ms |
31952 KB |
Output is correct |
16 |
Correct |
27 ms |
31952 KB |
Output is correct |
17 |
Correct |
28 ms |
31972 KB |
Output is correct |
18 |
Correct |
28 ms |
31972 KB |
Output is correct |
19 |
Correct |
29 ms |
31972 KB |
Output is correct |
20 |
Correct |
27 ms |
32008 KB |
Output is correct |
21 |
Correct |
30 ms |
32008 KB |
Output is correct |
22 |
Correct |
36 ms |
32136 KB |
Output is correct |
23 |
Correct |
31 ms |
32136 KB |
Output is correct |
24 |
Correct |
52 ms |
32204 KB |
Output is correct |
25 |
Correct |
67 ms |
32204 KB |
Output is correct |
26 |
Correct |
71 ms |
32204 KB |
Output is correct |
27 |
Correct |
81 ms |
32204 KB |
Output is correct |
28 |
Correct |
42 ms |
32204 KB |
Output is correct |