Submission #471176

Source Code Expand

#include <iostream>
#include <algorithm>

const int max = 100001;
const int mod = 1000000007;

int n;
int dp[4][max];
int d[max];

int main(){
	std::cin >> n;
	for(int i = 0; i < n; i++)std::cin >> d[i], dp[0][i] = 1;
	std::sort(d, d + n);
	for(int i = 1; i <= 3; i++){
		for(int j = 1; j < n; j++)dp[i - 1][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod;
		for(int j = 1; j < n; j++){
			int p = std::upper_bound(d, d + j, d[j] / 2) - d - 1;
			dp[i][j] = dp[i - 1][p] % mod;
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++)ans = (ans + dp[3][i]) % mod;
	std::cout << ans << std::endl;
	return 0;
}

Submission Info

Submission Time
Task B - 難易度
User Stack96
Language C++ (GCC 4.9.2)
Score 100
Code Size 624 Byte
Status AC
Exec Time 113 ms
Memory 2728 KiB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 3
AC × 22
AC × 43
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt
Case Name Status Exec Time Memory
sample_01.txt AC 25 ms 924 KiB
sample_02.txt AC 25 ms 804 KiB
sample_03.txt AC 25 ms 920 KiB
subtask1_01.txt AC 25 ms 732 KiB
subtask1_02.txt AC 23 ms 800 KiB
subtask1_03.txt AC 27 ms 932 KiB
subtask1_04.txt AC 26 ms 928 KiB
subtask1_05.txt AC 25 ms 924 KiB
subtask1_06.txt AC 26 ms 840 KiB
subtask1_07.txt AC 27 ms 920 KiB
subtask1_08.txt AC 28 ms 804 KiB
subtask1_09.txt AC 28 ms 796 KiB
subtask1_10.txt AC 26 ms 912 KiB
subtask1_11.txt AC 27 ms 792 KiB
subtask1_12.txt AC 27 ms 796 KiB
subtask1_13.txt AC 27 ms 840 KiB
subtask1_14.txt AC 27 ms 792 KiB
subtask1_15.txt AC 28 ms 924 KiB
subtask1_16.txt AC 28 ms 800 KiB
subtask1_17.txt AC 28 ms 912 KiB
subtask1_18.txt AC 27 ms 792 KiB
subtask1_19.txt AC 28 ms 916 KiB
subtask2_01.txt AC 49 ms 1324 KiB
subtask2_02.txt AC 48 ms 1256 KiB
subtask2_03.txt AC 33 ms 1056 KiB
subtask2_04.txt AC 36 ms 1060 KiB
subtask2_05.txt AC 94 ms 2344 KiB
subtask2_06.txt AC 85 ms 2088 KiB
subtask2_07.txt AC 30 ms 920 KiB
subtask2_08.txt AC 30 ms 912 KiB
subtask2_09.txt AC 98 ms 2340 KiB
subtask2_10.txt AC 67 ms 1692 KiB
subtask2_11.txt AC 29 ms 920 KiB
subtask2_12.txt AC 63 ms 1704 KiB
subtask2_13.txt AC 31 ms 928 KiB
subtask2_14.txt AC 76 ms 1948 KiB
subtask2_15.txt AC 111 ms 2720 KiB
subtask2_16.txt AC 113 ms 2720 KiB
subtask2_17.txt AC 109 ms 2716 KiB
subtask2_18.txt AC 111 ms 2716 KiB
subtask2_19.txt AC 111 ms 2712 KiB
subtask2_20.txt AC 85 ms 2728 KiB
subtask2_21.txt AC 81 ms 2728 KiB