Submission #1602535

---

Source Code Expand

import java.util.Arrays;
import java.util.Scanner;


public class Main
{
	static Scanner sc = new Scanner(System.in);
	final int BASE = 1000000007;
	
	int nInt()
	{
		return Integer.parseInt(sc.next());
	}

	public static void main(String[] args) throws Exception
	{
		new Main().run();
	}

	void run()
	{
		int n = nInt();
		int[] ds = new int[n+1];
		for(int i=1; i<=n; i++) ds[i] = nInt();
		Arrays.sort(ds);
		int[][] f = new int[n+1][];
		f[0] = new int[]{0, 0, 0, 0};
		for(int i=1; i<=n; i++)
		{
			int[] r = f[i-1].clone();
			int idx = Arrays.binarySearch(ds, ds[i]/2);
			if(idx<0) idx = -idx - 2;
			int[] floor = f[idx];
			r[0] += 1;
			r[1] += floor[0];
			r[2] += floor[1];
			r[3] += floor[2];
			for(int j=0; j<4; j++) r[j] %= BASE;
			f[i] = r;
		}
		System.out.println(f[n][3]);
	}
}

Submission Info

Judge Result