| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 448821 |
2021-08-01T22:36:03 Z |
gmyu |
Kangaroo (CEOI16_kangaroo) |
C++14 |
|
56 ms |
31664 KB |
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/CEOI16_kangaroo
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 2007
#define MAXE 100007
bool debug;
int N;
ll dp[MAXV][MAXV];
/** dp[i,j], count using 1 ...i, and break down into j continous blocks
* in each block, we start jump to a higher number, and end with jump to a lower number
* this way, each block can be connected (when connect 2 blocks, the 2nd block will flip its order of jump)
*/
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
int cs, cf;
cin >> N >> cs >> cf;
dp[1][1] = 1;
for(int i=2; i<=N; i++) {
for(int j=1; j<=N; j++) {
/// if i is the cs or cf, the only way is to start or end with i
/// if i-th is cs, it starts by merge with a block or form as its own block. Same as cf.
if(i==cs || i==cf) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
if(dp[i][j] > MOD) dp[i][j] %= MOD;
} else {
/// one way to form j blocks is to start with j+1 blocks and merge 2 blocks together, which is j ways
/// the i-th number is used to connect those 2 together (so the jump can turn around)
ll nc = ( dp[i-1][j+1] * (ll)j ) % MOD;
dp[i][j] = (dp[i][j] + nc) % MOD;
/// another way to form j blocks is to start with j-1 blocks and add i-th number as the extra block
/// there are j-1+1=j ways to place this extra block
/// note that if cs or cf <i, then the block contains cs or cf can not be moved
nc = ( dp[i-1][j-1] * (ll) (j - (cs<i) - (cf<i)) ) % MOD;
dp[i][j] = (dp[i][j] + nc) % MOD;
}
}
}
cout << dp[N][1] << endl;
if(debug) cout << endl << "EOL" << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
460 KB |
Output is correct |
| 10 |
Correct |
1 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
460 KB |
Output is correct |
| 10 |
Correct |
1 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
460 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1340 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1216 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 20 |
Correct |
1 ms |
1356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
460 KB |
Output is correct |
| 10 |
Correct |
1 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
460 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1340 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1216 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 20 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 21 |
Correct |
8 ms |
6268 KB |
Output is correct |
| 22 |
Correct |
10 ms |
6860 KB |
Output is correct |
| 23 |
Correct |
10 ms |
7756 KB |
Output is correct |
| 24 |
Correct |
56 ms |
31640 KB |
Output is correct |
| 25 |
Correct |
54 ms |
31664 KB |
Output is correct |
| 26 |
Correct |
55 ms |
31644 KB |
Output is correct |
| 27 |
Correct |
54 ms |
31460 KB |
Output is correct |
| 28 |
Correct |
34 ms |
23728 KB |
Output is correct |
