Submission #3855919

Source Code Expand

from collections import defaultdict
N,A,B,C,D=map(int,input().split())

mod=10**9+7
table=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
dp=defaultdict(int)
dp[N]=1
for l in range(A,B+1):
    ndp=defaultdict(int)
    for mem,num in dp.items():
        ndp[mem]+=num
        for k in range(C,D+1):
            if mem-k*l<0:
                break
            t=(table[mem]*pow(rtable[l],k,mod)*rtable[mem-k*l]*rtable[k])%mod
            ndp[mem-k*l]+=(num*t)%mod
            ndp[mem-k*l]%mod
            #print(mem-k*l,(num*t)%mod)

    dp=ndp
    #print(dp)
print(dp[0]%mod)

Submission Info

Submission Time
Task E - Grouping
User okumura
Language PyPy3 (2.4.0)
Score 600
Code Size 725 Byte
Status AC
Exec Time 1453 ms
Memory 74076 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 4
AC × 15
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_many_01.txt, subtask_1_many_02.txt, subtask_1_many_03.txt, subtask_1_many_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_min_01.txt, subtask_1_randa_01.txt, subtask_1_randa_02.txt, subtask_1_randb_01.txt, subtask_1_randb_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 172 ms 38384 KiB
sample_02.txt AC 168 ms 38256 KiB
sample_03.txt AC 1453 ms 74076 KiB
sample_04.txt AC 165 ms 38256 KiB
subtask_1_many_01.txt AC 1064 ms 56284 KiB
subtask_1_many_02.txt AC 960 ms 55132 KiB
subtask_1_many_03.txt AC 1033 ms 55516 KiB
subtask_1_many_04.txt AC 1112 ms 59484 KiB
subtask_1_max_01.txt AC 186 ms 39024 KiB
subtask_1_max_02.txt AC 186 ms 39024 KiB
subtask_1_min_01.txt AC 166 ms 38256 KiB
subtask_1_randa_01.txt AC 171 ms 38256 KiB
subtask_1_randa_02.txt AC 168 ms 38256 KiB
subtask_1_randb_01.txt AC 190 ms 40048 KiB
subtask_1_randb_02.txt AC 198 ms 40304 KiB