# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
792722 | 2023-07-25T08:17:13 Z | RecursiveCo | 캥거루 (CEOI16_kangaroo) | C++14 | 2000 ms | 71508 KB |
// CF template, version 3.0 #include <bits/stdc++.h> using namespace std; #define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0) #define getTest int t; cin >> t #define eachTest for (int _var=0;_var<t;_var++) #define get(name) int (name); cin >> (name) #define out(o) cout << (o) #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); } #define sortl(name) sort((name).begin(), (name).end()) #define rev(name) reverse((name).begin(), (name).end()) #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++) #define decision(b) if (b){out("YES");}else{out("NO");} #define int long long int int mod = 1e9 + 7; signed main() { improvePerformance; get(n); get(a); get(b); a--; b--; vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, 0))); vector<vector<vector<int>>> newdp(n, vector<vector<int>>(n, vector<int>(2, 0))); vector<vector<vector<int>>> oldpref(n, vector<vector<int>>(n, vector<int>(2, 0))); // dp[j][i][0]: left // dp[j][i][1]: right dp[1][0][0] = 0; dp[1][0][1] = 1; dp[0][1][0] = 1; dp[0][1][1] = 0; for (int c = 2; c < n; c++) { forto(c, j) { forto(c, i) { forto(2, d) { if (i == 0) oldpref[j][i][d] = dp[j][i][d]; else oldpref[j][i][d] = (oldpref[j][i - 1][d] + dp[j][i][d]) % mod; } } } forto(c + 1, i) { forto(c + 1, j) { if (i == j) continue; // going left. int left; if (i < j) left = i? oldpref[j - 1][i - 1][1]: 0; else left = i? oldpref[j][i - 1][1]: 0; newdp[j][i][0] = left; int right; if (i < j) right = (oldpref[j - 1][c - 1][0] + mod - (i? oldpref[j - 1][i - 1][0]: 0)) % mod; else right = (oldpref[j][c - 1][0] + mod - (i? oldpref[j][i - 1][0]: 0)) % mod; newdp[j][i][1] = right; } } swap(dp, newdp); } out((dp[b][a][0] + dp[b][a][1]) % mod); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 580 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 2 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 580 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 2 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 49 ms | 6840 KB | Output is correct |
13 | Correct | 37 ms | 6072 KB | Output is correct |
14 | Correct | 45 ms | 6848 KB | Output is correct |
15 | Correct | 50 ms | 6948 KB | Output is correct |
16 | Correct | 44 ms | 6740 KB | Output is correct |
17 | Correct | 45 ms | 6868 KB | Output is correct |
18 | Correct | 37 ms | 5552 KB | Output is correct |
19 | Correct | 43 ms | 6708 KB | Output is correct |
20 | Correct | 43 ms | 6848 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 580 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 2 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 49 ms | 6840 KB | Output is correct |
13 | Correct | 37 ms | 6072 KB | Output is correct |
14 | Correct | 45 ms | 6848 KB | Output is correct |
15 | Correct | 50 ms | 6948 KB | Output is correct |
16 | Correct | 44 ms | 6740 KB | Output is correct |
17 | Correct | 45 ms | 6868 KB | Output is correct |
18 | Correct | 37 ms | 5552 KB | Output is correct |
19 | Correct | 43 ms | 6708 KB | Output is correct |
20 | Correct | 43 ms | 6848 KB | Output is correct |
21 | Execution timed out | 2066 ms | 71508 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |