# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52952 |
2018-06-27T08:38:47 Z |
강태규(#1381) |
Kangaroo (CEOI16_kangaroo) |
C++11 |
|
37 ms |
31876 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;
}
//printf("u1[%d][%d]=%d\n", n, e, ret);
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 - 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 |
31 ms |
31608 KB |
Output is correct |
2 |
Correct |
26 ms |
31716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
31608 KB |
Output is correct |
2 |
Correct |
26 ms |
31716 KB |
Output is correct |
3 |
Correct |
26 ms |
31876 KB |
Output is correct |
4 |
Incorrect |
37 ms |
31876 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
31608 KB |
Output is correct |
2 |
Correct |
26 ms |
31716 KB |
Output is correct |
3 |
Correct |
26 ms |
31876 KB |
Output is correct |
4 |
Incorrect |
37 ms |
31876 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
31608 KB |
Output is correct |
2 |
Correct |
26 ms |
31716 KB |
Output is correct |
3 |
Correct |
26 ms |
31876 KB |
Output is correct |
4 |
Incorrect |
37 ms |
31876 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |