| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125569 |
2019-07-06T01:03:40 Z |
tutis |
Kangaroo (CEOI16_kangaroo) |
C++17 |
|
2000 ms |
204600 KB |
/*input
10 2 3
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll modulo = 1000000007;
ll fast(int N, int A, int B)
{
ll L[N + 1][N + 1][N + 1];
ll R[N + 1][N + 1][N + 1];
for (int n = 2; n <= N; n++)
{
for (int a = 1; a <= n; a++)
{
L[n][a][0] = 0;
R[n][a][0] = 0;
for (int b = 1; b <= n; b++)
{
L[n][a][b] = L[n][a][b - 1];
R[n][a][b] = R[n][a][b - 1];
if (a == b)
continue;
if (n == 2)
{
if (a > b)
{
L[n][a][b] = 1;
}
if (a < b)
{
R[n][a][b] = 1;
}
}
else
{
L[n][a][b] += R[n - 1][a - (a > b)][n - 1];
L[n][a][b] -= R[n - 1][a - (a > b)][b - 1];
R[n][a][b] += L[n - 1][a - (a > b)][b - 1];
}
L[n][a][b] %= modulo;
R[n][a][b] %= modulo;
}
}
}
ll ret = L[N][A][B] - L[N][A][B - 1] + R[N][A][B] - R[N][A][B - 1];
ret %= modulo;
ret += modulo;
ret %= modulo;
return ret;
}
ll R(int n, int a, int b);
map<tuple<int, int, int>, int>LL;
ll L(int n, int a, int b)
{
if (LL.count(make_tuple(n, a, b)))
return LL[make_tuple(n, a, b)];
if (b == 0)
return 0;
ll ret = L(n, a, b - 1);
if (a == b)
return LL[make_tuple(n, a, b)] = ret;
if (n == 2)
{
if (a > b)
ret++;
}
else
{
ret += R(n - 1, a - (a > b), n - 1);
ret -= R(n - 1, a - (a > b), b - 1);
}
ret %= modulo;
return LL[make_tuple(n, a, b)] = ret;
}
map<tuple<int, int, int>, int>RR;
ll R(int n, int a, int b)
{
if (RR.count(make_tuple(n, a, b)))
return RR[make_tuple(n, a, b)];
if (b == 0)
return 0;
ll ret = R(n, a, b - 1);
if (a == b)
return RR[make_tuple(n, a, b)] = ret;
if (n == 2)
{
if (a < b)
ret++;
}
else
{
ret += L(n - 1, a - (a > b), b - 1);
}
ret %= modulo;
return RR[make_tuple(n, a, b)] = ret;
}
ll faster(int N, int A, int B)
{
ll ret = L(N, A, B) - L(N, A, B - 1) + R(N, A, B) - R(N, A, B - 1);
ret %= modulo;
ret += modulo;
ret %= modulo;
return ret;
}
int main()
{
int n, a, b;
cin >> n >> a >> b;
//cout << fast(n, a, b) << "\n";
cout << faster(n, a, b) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1016 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1400 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 11 |
Correct |
4 ms |
636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1016 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1400 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 11 |
Correct |
4 ms |
636 KB |
Output is correct |
| 12 |
Correct |
1436 ms |
123296 KB |
Output is correct |
| 13 |
Correct |
59 ms |
7772 KB |
Output is correct |
| 14 |
Correct |
46 ms |
6392 KB |
Output is correct |
| 15 |
Correct |
897 ms |
82088 KB |
Output is correct |
| 16 |
Correct |
1413 ms |
121984 KB |
Output is correct |
| 17 |
Correct |
1252 ms |
112744 KB |
Output is correct |
| 18 |
Correct |
273 ms |
28600 KB |
Output is correct |
| 19 |
Correct |
936 ms |
83824 KB |
Output is correct |
| 20 |
Correct |
748 ms |
70780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1016 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1400 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 11 |
Correct |
4 ms |
636 KB |
Output is correct |
| 12 |
Correct |
1436 ms |
123296 KB |
Output is correct |
| 13 |
Correct |
59 ms |
7772 KB |
Output is correct |
| 14 |
Correct |
46 ms |
6392 KB |
Output is correct |
| 15 |
Correct |
897 ms |
82088 KB |
Output is correct |
| 16 |
Correct |
1413 ms |
121984 KB |
Output is correct |
| 17 |
Correct |
1252 ms |
112744 KB |
Output is correct |
| 18 |
Correct |
273 ms |
28600 KB |
Output is correct |
| 19 |
Correct |
936 ms |
83824 KB |
Output is correct |
| 20 |
Correct |
748 ms |
70780 KB |
Output is correct |
| 21 |
Execution timed out |
2077 ms |
204600 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
