Submission #667286

#	Time	Username	Problem	Language	Result	Execution time	Memory
667286		ziduo	Kangaroo (CEOI16_kangaroo)	Java	100 / 100	142 ms	41488 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());
	    long[][] dp = new long[n+1][n+1];
	    if(s>e) {
	    	int save = s;
	    	s = e;
	    	e = save;
	    }
	    long mod = 1000000007;
	    dp[1][1] = 1;
	    for(int i=2; i<=n; i++) {
	    	for(int j=1; j<=i; j++) {
	    		if(dp[i-1][j]==0)continue;
	    		if(i==s||i==e) {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j])%mod;
	    			dp[i][j] = (dp[i][j]+dp[i-1][j])%mod;
	    			continue;
	    		}
	    		if(i<s) {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j]*(j+1))%mod;
	    			dp[i][j-1] = (dp[i][j-1]+dp[i-1][j]*(j-1))%mod;
	    		}
	    		else if(i>s&&i<e) {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j]*(j))%mod;
	    			dp[i][j-1] = (dp[i][j-1]+dp[i-1][j]*(j-1))%mod;	    			
	    		}
	    		else {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j]*(j-1))%mod;
	    			dp[i][j-1] = (dp[i][j-1]+dp[i-1][j]*(j-1))%mod;	   	
	    		}
	    	}
	    }
	    System.out.println(dp[n][1]);
	}
}

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