이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class kangaroo {
static int[][] X;
static int v;
static int[][][] dp;
public static void main(String[] args)throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
dp = new int[n+1][3][n+1];
for(int i=1; i<3; i++) dp[1][i][i] =1;
for(int i=1; i<3; i++)for(int j=1; j<=n; j++)if(i!=j)dp[2][i][j]=1;
for(int i=3; i<=n; i++) {
if(i%2==0) {
for(int k=4 ; k<=n; k++) {
dp[i][1][k] = dp[i][1][k-1]+dp[i-1][1][k-1];
}
}
else {
for(int k=n-1; k>1; k--) {
dp[i][1][k] = dp[i-1][1][k]+dp[i][1][k+1];
}
}
}
for(int i=2; i<=n; i++) {
for(int k=1; k<=n; k++) {
dp[i][2][k] = dp[i][1][k] + dp[i-1][1][k-1];
}
}
if(s>e) s = (e+s-(e=s));
v = n-e;
System.out.println(rec(n, s));
}
static int rec(int n, int i) {
if(n-v<=0)return 0;
if(i<3)return dp[n][i][n-v];
if(X[n][i]!=-1)return X[n][i];
X[n][i] = (2*rec(n,i-1)-rec(n,i-2)-rec(n-1,i-2));
if(X[n][i]<0)X[n][i]+=2000000014;
X[n][i]%=1000000007;
return X[n][i];
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |