Submission #373909

#	Time	Username	Problem	Language	Result	Execution time	Memory
373909		jfyen	A Huge Tower (CEOI10_tower)	Java	85 / 100	1095 ms	27896 KiB

tower

import java.util.*;
public class tower {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int D = sc.nextInt();
		long mod = 1000000009;
		int[] blocks = new int[N];
		for (int i = 0;i<N;i++) {
			blocks[i] = sc.nextInt();
		}
		Arrays.sort(blocks);
		long[] place = new long[N];
		long[] towers = new long[N];
		towers[0] = 1;
		//place[0] = 1;
		int lower = 0;
		for (int i = 0;i<N;i++) {
			while(lower<i) {
				if(blocks[lower]+D<blocks[i])
					lower++;
				else
					break;
			}
			//System.out.println(i+" "+lower);
			place[i] = (i-lower+1)%mod;
		}
		//System.out.println(Arrays.toString(place));
		for (int i = 1;i<N;i++) {
			towers[i] = (place[i]*towers[i-1])%mod;
		}
		System.out.println(towers[N-1]%mod);
	}

}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5