# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
966820 |
2024-04-20T12:16:12 Z |
berr |
Kangaroo (CEOI16_kangaroo) |
C++17 |
|
2000 ms |
63508 KB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+5, mod=1e9+7;
vector<vector<array<int, 2>>> dp(N, vector<array<int, 2>>(N, array<int, 2>{0LL, 0LL}));
vector<vector<array<int, 2>>> dpn(N, vector<array<int, 2>>(N, array<int, 2>{0LL, 0LL}));
int calc(int n, int cs, int cf, int dir){
if(cs==cf) return dpn[cs][cf][dir]=0;
if(dpn[cs][cf][dir]!=-1) return dpn[cs][cf][dir];
if(n==2 && (cs<cf)==dir) return dpn[cs][cf][dir]=1;
if(n==2) return dpn[cs][cf][dir]=0;
if(dir == 1 && cs==n-1) return dpn[cs][cf][dir]=0;
else if(dir==0 && cs==0) return dpn[cs][cf][dir]=0;;
int v=0, check=0, ans=0;
if(dir==0){
ans+=dp[cs-1][cf-(cs<cf)][1];
}
else{
int v=cs;
ans+=dp[v][cf-(cs<cf)][0];
}
return dpn[cs][cf][dir]=ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
/* freopen("kangaroo.in", "r", stdin);
freopen("kangaroo.out", "w", stdout);
*/
int n, cs, cf; cin >> n >> cs >> cf;
cs--; cf--;
for(int i=2; i<n; i++){
for(int l=0; l<=i; l++){
for(int j=0; j<=i; j++){
for(int x=0; x<2; x++){
dpn[l][j][x] =-1;
}
}
}
for(int l=0; l<i; l++){
for(int j=0; j<i; j++){
for(int x=0; x<2; x++){
dpn[l][j][x] = calc(i, l, j, x);
}
}
}
for(int l=i-2; l>=0; l--){
for(int j=0; j<i; j++){
dpn[l][j][0]+=dpn[l+1][j][0];
dpn[l][j][0] %= mod;
}
}
for(int l=1; l<i; l++){
for(int j=0; j<i; j++){
dpn[l][j][1] += dpn[l-1][j][1];
dpn[l][j][1] %= mod;
}
}
swap(dpn, dp);
}
for(int l=0; l<=n; l++){
for(int j=0; j<=n; j++){
for(int x=0; x<2; x++){
dpn[l][j][x] =-1;
}
}
}
cout<<((calc(n, cs, cf, 0)+calc(n, cs, cf, 1))%mod);
// cout<<"tamam";
}
Compilation message
kangaroo.cpp: In function 'int calc(int, int, int, int)':
kangaroo.cpp:20:9: warning: unused variable 'v' [-Wunused-variable]
20 | int v=0, check=0, ans=0;
| ^
kangaroo.cpp:20:14: warning: unused variable 'check' [-Wunused-variable]
20 | int v=0, check=0, ans=0;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
63320 KB |
Output is correct |
2 |
Correct |
27 ms |
63324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
63320 KB |
Output is correct |
2 |
Correct |
27 ms |
63324 KB |
Output is correct |
3 |
Correct |
28 ms |
63420 KB |
Output is correct |
4 |
Correct |
28 ms |
63324 KB |
Output is correct |
5 |
Correct |
28 ms |
63312 KB |
Output is correct |
6 |
Correct |
27 ms |
63328 KB |
Output is correct |
7 |
Correct |
28 ms |
63316 KB |
Output is correct |
8 |
Correct |
27 ms |
63312 KB |
Output is correct |
9 |
Correct |
27 ms |
63320 KB |
Output is correct |
10 |
Correct |
27 ms |
63324 KB |
Output is correct |
11 |
Correct |
29 ms |
63324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
63320 KB |
Output is correct |
2 |
Correct |
27 ms |
63324 KB |
Output is correct |
3 |
Correct |
28 ms |
63420 KB |
Output is correct |
4 |
Correct |
28 ms |
63324 KB |
Output is correct |
5 |
Correct |
28 ms |
63312 KB |
Output is correct |
6 |
Correct |
27 ms |
63328 KB |
Output is correct |
7 |
Correct |
28 ms |
63316 KB |
Output is correct |
8 |
Correct |
27 ms |
63312 KB |
Output is correct |
9 |
Correct |
27 ms |
63320 KB |
Output is correct |
10 |
Correct |
27 ms |
63324 KB |
Output is correct |
11 |
Correct |
29 ms |
63324 KB |
Output is correct |
12 |
Correct |
42 ms |
63500 KB |
Output is correct |
13 |
Correct |
38 ms |
63320 KB |
Output is correct |
14 |
Correct |
40 ms |
63324 KB |
Output is correct |
15 |
Correct |
40 ms |
63496 KB |
Output is correct |
16 |
Correct |
42 ms |
63320 KB |
Output is correct |
17 |
Correct |
40 ms |
63508 KB |
Output is correct |
18 |
Correct |
37 ms |
63320 KB |
Output is correct |
19 |
Correct |
46 ms |
63404 KB |
Output is correct |
20 |
Correct |
40 ms |
63508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
63320 KB |
Output is correct |
2 |
Correct |
27 ms |
63324 KB |
Output is correct |
3 |
Correct |
28 ms |
63420 KB |
Output is correct |
4 |
Correct |
28 ms |
63324 KB |
Output is correct |
5 |
Correct |
28 ms |
63312 KB |
Output is correct |
6 |
Correct |
27 ms |
63328 KB |
Output is correct |
7 |
Correct |
28 ms |
63316 KB |
Output is correct |
8 |
Correct |
27 ms |
63312 KB |
Output is correct |
9 |
Correct |
27 ms |
63320 KB |
Output is correct |
10 |
Correct |
27 ms |
63324 KB |
Output is correct |
11 |
Correct |
29 ms |
63324 KB |
Output is correct |
12 |
Correct |
42 ms |
63500 KB |
Output is correct |
13 |
Correct |
38 ms |
63320 KB |
Output is correct |
14 |
Correct |
40 ms |
63324 KB |
Output is correct |
15 |
Correct |
40 ms |
63496 KB |
Output is correct |
16 |
Correct |
42 ms |
63320 KB |
Output is correct |
17 |
Correct |
40 ms |
63508 KB |
Output is correct |
18 |
Correct |
37 ms |
63320 KB |
Output is correct |
19 |
Correct |
46 ms |
63404 KB |
Output is correct |
20 |
Correct |
40 ms |
63508 KB |
Output is correct |
21 |
Correct |
513 ms |
63508 KB |
Output is correct |
22 |
Correct |
588 ms |
63320 KB |
Output is correct |
23 |
Correct |
750 ms |
63504 KB |
Output is correct |
24 |
Execution timed out |
2033 ms |
63320 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |