Submission #34405886

Source Code Expand

##1000000 1000000 1000000 1000000
R,G,B,K = map(int,input().split())

def comb(n,k):
    nCk = 1
    MOD = 998244353

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

if min(R,G) < K : 
    print(0)
    exit(0)

_K = min (R,G)

dp = [0] * (R+G+B+1)
cum = [0] * (R+G+B+1)
dp[_K] = comb(R+G+B-_K, B) * comb (R+G-_K, _K) * comb (R+G-2*_K, max(R,G)-_K ) 
cum[_K] = dp[_K]
for i in range(_K-1,K-1,-1) : 
    dp[i] = comb(R+G+B-i, B) * comb (R+G-i, i) * comb (R+G-2*i, max(R,G)-i ) - cum [i+1]   
    cum[i] = cum[i+1] + dp[i] 

print( dp[K] )

Submission Info

Submission Time
Task G - Yet Another RGB Sequence
User ay24h
Language PyPy3 (7.3.0)
Score 0
Code Size 683 Byte
Status WA
Exec Time 2212 ms
Memory 205860 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 2
AC × 4
WA × 4
TLE × 27
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt
All 00_sample_01.txt, 00_sample_02.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 03_large_01.txt, 03_large_02.txt, 03_large_03.txt, 03_large_04.txt, 03_large_05.txt, 03_large_06.txt, 03_large_07.txt, 03_large_08.txt, 03_large_09.txt, 03_large_10.txt, 03_large_11.txt, 03_large_12.txt, 03_large_13.txt, 03_large_14.txt, 03_large_15.txt, 03_large_16.txt, 03_large_17.txt, 03_large_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 78 ms 61804 KiB
00_sample_02.txt AC 1290 ms 110648 KiB
01_small_01.txt AC 66 ms 61888 KiB
01_small_02.txt AC 49 ms 62032 KiB
01_small_03.txt WA 47 ms 62060 KiB
01_small_04.txt WA 54 ms 64132 KiB
01_small_05.txt WA 50 ms 61884 KiB
02_random_01.txt TLE 2210 ms 140604 KiB
02_random_02.txt TLE 2210 ms 124976 KiB
02_random_03.txt TLE 2210 ms 139612 KiB
02_random_04.txt TLE 2211 ms 168964 KiB
02_random_05.txt TLE 2210 ms 130120 KiB
02_random_06.txt TLE 2210 ms 133496 KiB
02_random_07.txt TLE 2208 ms 95284 KiB
02_random_08.txt TLE 2211 ms 163396 KiB
02_random_09.txt TLE 2210 ms 136216 KiB
02_random_10.txt TLE 2211 ms 167488 KiB
03_large_01.txt TLE 2210 ms 132352 KiB
03_large_02.txt TLE 2210 ms 141844 KiB
03_large_03.txt TLE 2208 ms 97000 KiB
03_large_04.txt TLE 2212 ms 205860 KiB
03_large_05.txt TLE 2209 ms 110860 KiB
03_large_06.txt TLE 2209 ms 111104 KiB
03_large_07.txt TLE 2209 ms 111064 KiB
03_large_08.txt TLE 2209 ms 110952 KiB
03_large_09.txt TLE 2209 ms 111048 KiB
03_large_10.txt TLE 2209 ms 111084 KiB
03_large_11.txt TLE 2209 ms 111124 KiB
03_large_12.txt TLE 2209 ms 111164 KiB
03_large_13.txt TLE 2209 ms 110812 KiB
03_large_14.txt TLE 2209 ms 111100 KiB
03_large_15.txt WA 1306 ms 110672 KiB
03_large_16.txt TLE 2209 ms 111176 KiB
03_large_17.txt TLE 2209 ms 111164 KiB
03_large_18.txt TLE 2209 ms 111132 KiB