Submission #489908

Source Code Expand

n = input()
difs = [input() for _ in range(n)]
difs.sort()

ps = [0 for _ in range(n)]

j = 1
for i in range(n-1):
    while j < n and difs[i]*2 > difs[j]:
        j += 1
    ps[i] = j % n

dp = [[0 for _ in range(n+1)] for _ in range(5)]
for c in range(4-1, -1, -1):
    for i in range(n-1, -1, -1):
        if c == 3:
            dp[c][i] = 1 + dp[c][i+1]
        else:
            j = ps[i]
            if j:
                dp[c][i] = dp[c+1][j] + dp[c][i+1]
            else:
                dp[c][i] = 0
print dp[0][0] % 1000000007

Submission Info

Submission Time
Task B - 難易度
User lackdog
Language Python (2.7.3)
Score 100
Code Size 562 Byte
Status AC
Exec Time 1759 ms
Memory 20128 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 60 ms 3372 KiB
sample_02.txt AC 57 ms 3368 KiB
sample_03.txt AC 58 ms 3368 KiB
subtask1_01.txt AC 61 ms 3368 KiB
subtask1_02.txt AC 65 ms 3376 KiB
subtask1_03.txt AC 101 ms 3756 KiB
subtask1_04.txt AC 89 ms 3624 KiB
subtask1_05.txt AC 87 ms 3620 KiB
subtask1_06.txt AC 109 ms 3752 KiB
subtask1_07.txt AC 86 ms 3616 KiB
subtask1_08.txt AC 98 ms 3744 KiB
subtask1_09.txt AC 100 ms 3804 KiB
subtask1_10.txt AC 78 ms 3488 KiB
subtask1_11.txt AC 96 ms 3748 KiB
subtask1_12.txt AC 100 ms 3748 KiB
subtask1_13.txt AC 79 ms 3512 KiB
subtask1_14.txt AC 88 ms 3628 KiB
subtask1_15.txt AC 106 ms 3752 KiB
subtask1_16.txt AC 105 ms 3888 KiB
subtask1_17.txt AC 105 ms 3764 KiB
subtask1_18.txt AC 103 ms 3752 KiB
subtask1_19.txt AC 103 ms 3756 KiB
subtask2_01.txt AC 561 ms 8380 KiB
subtask2_02.txt AC 491 ms 7648 KiB
subtask2_03.txt AC 258 ms 5296 KiB
subtask2_04.txt AC 290 ms 5676 KiB
subtask2_05.txt AC 1399 ms 16448 KiB
subtask2_06.txt AC 1226 ms 14992 KiB
subtask2_07.txt AC 125 ms 4004 KiB
subtask2_08.txt AC 125 ms 4008 KiB
subtask2_09.txt AC 1467 ms 17316 KiB
subtask2_10.txt AC 908 ms 11684 KiB
subtask2_11.txt AC 140 ms 4236 KiB
subtask2_12.txt AC 830 ms 11116 KiB
subtask2_13.txt AC 175 ms 4520 KiB
subtask2_14.txt AC 1106 ms 13520 KiB
subtask2_15.txt AC 1720 ms 20048 KiB
subtask2_16.txt AC 1705 ms 20120 KiB
subtask2_17.txt AC 1710 ms 20120 KiB
subtask2_18.txt AC 1718 ms 20120 KiB
subtask2_19.txt AC 1759 ms 20128 KiB
subtask2_20.txt AC 1684 ms 19732 KiB
subtask2_21.txt AC 1711 ms 19220 KiB