oj.uz

답안 #30664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30664 2017-07-26T03:47:17 Z jenkhai 캥거루 (CEOI16_kangaroo) C++14
0 / 100
 0 ms 65144 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 65144 KB Output is correct
2 Incorrect 0 ms 65144 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 65144 KB Output is correct
2 Incorrect 0 ms 65144 KB Output isn't correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 65144 KB Output is correct
2 Incorrect 0 ms 65144 KB Output isn't correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 65144 KB Output is correct
2 Incorrect 0 ms 65144 KB Output isn't correct