Submission #30664

#	Time	Username	Problem	Language	Result	Execution time	Memory
30664		jenkhai	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	0 ms	65144 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int LEFT = 0;
const int RIGHT = 1;
const int MAXN = 2010;
int N, src, dst;
long long dp[MAXN][MAXN][2];

long long f(int i, int s, int a) {
    if(dp[i][s][a] != -1) return dp[i][s][a];
    dp[i][s][a] = 0;
    if(a==LEFT) {
        for(int j=1;j<i;j++) {
            if(f(j, s-1, RIGHT) == 0) continue;
            dp[i][s][a] = (dp[i][s][a] + f(j, s-1, RIGHT))%MOD;
            dp[i][s][a] = (dp[i][s][a] - f(i, s-2, LEFT))%MOD;
        } 
    } else {
        for(int j=i+1;j<=N;j++) {
            if(f(j, s-1, LEFT) == 0) continue;
            dp[i][s][a] = (dp[i][s][a] + f(j, s-1, LEFT))%MOD;
            dp[i][s][a] = (dp[i][s][a] - f(i, s-2, RIGHT))%MOD;
            if(dp[i][s][a] < 0) dp[i][s][a] += MOD;
        } 
    }
    return dp[i][s][a];
}


int main() {    
    scanf("%d %d %d", &N, &src, &dst); 
    for(int i=1;i<=N;i++) {
        dp[i][0][LEFT] = 0;
        dp[i][0][RIGHT] = 0;
        if(src<i) {
            dp[i][1][LEFT] = 1;
            dp[i][1][RIGHT] = 0;
        } else if(src>i){
            dp[i][1][LEFT] = 0;
            dp[i][1][RIGHT] = 1;
        }

        for(int j=2;j<=N;j++) {
            dp[i][j][0] = -1;
            dp[i][j][1] = -1;
        }
    }
    dp[src][0][0] = 1;
    dp[src][0][1] = 1;
    //for(int i=1;i<=N;i++) {
    //    for(int s=0;s<N;s++) {
    //        printf("%d %d LEFT: %d\n", i, s, dp[i][s][LEFT]);
    //        printf("%d %d RIGHT: %d\n", i, s, dp[i][s][RIGHT]);
    //    }
    //}
    printf("%lld\n", (f(dst, N-1, LEFT)+f(dst, N-1, RIGHT))%MOD);
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:32:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &src, &dst); 
                                      ^

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