Submission #448821

#	Time	Username	Problem	Language	Result	Execution time	Memory
448821		gmyu	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	56 ms	31664 KiB

kangaroo

/*
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;

}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49