Submission #661230

#	Time	Username	Problem	Language	Result	Execution time	Memory
661230		ziduo	Kangaroo (CEOI16_kangaroo)	Java	0 / 100	69 ms	8084 KiB

kangaroo

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];
	    X = new int[n+1][n+1];
	    for(int i=0; i<=n; i++)Arrays.fill(X[i], -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];
	}
}

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