# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
257580 |
2020-08-04T12:32:34 Z |
wzy |
Kangaroo (CEOI16_kangaroo) |
C++11 |
|
61 ms |
27128 KB |
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <climits>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x) , end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
ll modpow(ll b, ll e ,ll mod){
ll ans = 1;
for (; e; b = b * b % mod, e /= 2)
if (e & 1) ans = ans * b % mod;
return ans;
}
const int N = 2002;
const int mod = (int) 1e9 + 7;
ll dp[N][N];
bool vis[N][N];
int n , s , t;
ll solve(int x , int y ){
if(y < 0) return 0;
if(x == n + 1){
return (y == 1);
}
if(vis[x][y]) return dp[x][y];
dp[x][y] = 0 , vis[x][y]= 1;
int ok = y - (x >= s) - (x >= t);
if(x == s || x == t){
return dp[x][y] = (solve(x+1,y) + solve(x+1,y+1))%mod;
}
dp[x][y] = (dp[x][y] + 1ll * solve(x+1,y+1)*(ok + 1) + 1ll*solve(x+1,y-1)*(y-1)) %mod;
return dp[x][y];
}
int32_t main(){
cin >> n >> s >> t;
cout << solve(1, 0) << endl;
}
/* clever stuff:
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and STAY ORGANIZED
* Keep it simple stupid
* WRITE STUFF DOWN
* math -> gcd / lcm / divisors?
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
0 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
0 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
1664 KB |
Output is correct |
13 |
Correct |
1 ms |
1536 KB |
Output is correct |
14 |
Correct |
1 ms |
1712 KB |
Output is correct |
15 |
Correct |
1 ms |
1664 KB |
Output is correct |
16 |
Correct |
2 ms |
1664 KB |
Output is correct |
17 |
Correct |
1 ms |
1664 KB |
Output is correct |
18 |
Correct |
2 ms |
1536 KB |
Output is correct |
19 |
Correct |
2 ms |
1664 KB |
Output is correct |
20 |
Correct |
1 ms |
1664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
0 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
1664 KB |
Output is correct |
13 |
Correct |
1 ms |
1536 KB |
Output is correct |
14 |
Correct |
1 ms |
1712 KB |
Output is correct |
15 |
Correct |
1 ms |
1664 KB |
Output is correct |
16 |
Correct |
2 ms |
1664 KB |
Output is correct |
17 |
Correct |
1 ms |
1664 KB |
Output is correct |
18 |
Correct |
2 ms |
1536 KB |
Output is correct |
19 |
Correct |
2 ms |
1664 KB |
Output is correct |
20 |
Correct |
1 ms |
1664 KB |
Output is correct |
21 |
Correct |
7 ms |
6016 KB |
Output is correct |
22 |
Correct |
7 ms |
6528 KB |
Output is correct |
23 |
Correct |
8 ms |
7168 KB |
Output is correct |
24 |
Correct |
59 ms |
27004 KB |
Output is correct |
25 |
Correct |
59 ms |
27000 KB |
Output is correct |
26 |
Correct |
55 ms |
27128 KB |
Output is correct |
27 |
Correct |
61 ms |
26872 KB |
Output is correct |
28 |
Correct |
36 ms |
18168 KB |
Output is correct |