Submission #20093563

Source Code Expand

#!/usr/local/bin/pypy3
import sys
readline = sys.stdin.buffer.readline

mod=998244353

vmax=3010
fact=[1]*vmax
finv=[1]*vmax
invs=[0]*vmax
fact[0]=1
for i in range(1,vmax):
	fact[i]=fact[i-1]*i%mod
finv[vmax-1]=pow(fact[vmax-1],mod-2,mod)
for i in range(vmax-2,-1,-1):
	finv[i]=finv[i+1]*(i+1)%mod
for i in range(vmax-1,0,-1):
	invs[i]=finv[i]*fact[i-1]%mod
def binom(a,b):
	return fact[a+b]*finv[a]%mod*finv[b]%mod

n,m=map(int,readline().split())
tar=list(map(int,readline().split()))

dp=[0]*(n+1)
dp[0]=1
nx=[0]*(n+1)
for _ in range(m):
	nx[0]=0
	for i in range(1,n+1):
		nx[i]=(dp[i-1]+dp[i]*i*2)%mod
	dp,nx=nx,dp

ans=0
for l in range(n+1):
	for r in range(l,n+1):
		if l+2<=r and tar[r-2]>tar[r-1]:
			break
		ans+=dp[n-(r-l)]*binom(l,n-r)%mod

print(ans%mod)

Submission Info

Submission Time
Task E - Cigar Box
User maroonrk_admin
Language PyPy3 (7.3.0)
Score 700
Code Size 810 Byte
Status AC
Exec Time 161 ms
Memory 68696 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 36
Set Name Test Cases
Sample sample.txt, sample_2.txt, sample_3.txt
All dec_1097_1362.txt, dec_1214_138.txt, dec_2404_801.txt, dec_2886_2657.txt, dec_754_2194.txt, inc_2393_1050.txt, inc_2728_537.txt, inc_325_982.txt, inc_728_2645.txt, inc_786_1704.txt, random_102_2522.txt, random_1326_1061.txt, random_1421_916.txt, random_146_5.txt, random_1559_262.txt, random_16_157.txt, random_1775_2266.txt, random_2015_811.txt, random_20_1776.txt, random_222_41.txt, random_27_10.txt, random_2993_1514.txt, random_2_4.txt, random_333_1061.txt, random_360_208.txt, random_4_23.txt, random_501_2539.txt, random_781_1616.txt, random_7_203.txt, random_89_890.txt, sample.txt, sample_2.txt, sample_3.txt, sorted_3000_1.txt, sorted_3000_300.txt, sorted_3000_3000.txt
Case Name Status Exec Time Memory
dec_1097_1362.txt AC 126 ms 68440 KiB
dec_1214_138.txt AC 72 ms 68628 KiB
dec_2404_801.txt AC 77 ms 68548 KiB
dec_2886_2657.txt AC 97 ms 68536 KiB
dec_754_2194.txt AC 76 ms 68072 KiB
inc_2393_1050.txt AC 88 ms 68696 KiB
inc_2728_537.txt AC 94 ms 68596 KiB
inc_325_982.txt AC 75 ms 68140 KiB
inc_728_2645.txt AC 85 ms 68208 KiB
inc_786_1704.txt AC 81 ms 68388 KiB
random_102_2522.txt AC 65 ms 68200 KiB
random_1326_1061.txt AC 82 ms 68456 KiB
random_1421_916.txt AC 77 ms 68588 KiB
random_146_5.txt AC 60 ms 65856 KiB
random_1559_262.txt AC 77 ms 68368 KiB
random_16_157.txt AC 62 ms 68432 KiB
random_1775_2266.txt AC 89 ms 68372 KiB
random_2015_811.txt AC 82 ms 68280 KiB
random_20_1776.txt AC 62 ms 68008 KiB
random_222_41.txt AC 62 ms 67692 KiB
random_27_10.txt AC 57 ms 65732 KiB
random_2993_1514.txt AC 88 ms 68276 KiB
random_2_4.txt AC 59 ms 65608 KiB
random_333_1061.txt AC 70 ms 68160 KiB
random_360_208.txt AC 65 ms 68264 KiB
random_4_23.txt AC 60 ms 65692 KiB
random_501_2539.txt AC 72 ms 68240 KiB
random_781_1616.txt AC 74 ms 68320 KiB
random_7_203.txt AC 62 ms 67660 KiB
random_89_890.txt AC 62 ms 68300 KiB
sample.txt AC 57 ms 65356 KiB
sample_2.txt AC 59 ms 65544 KiB
sample_3.txt AC 67 ms 68236 KiB
sorted_3000_1.txt AC 117 ms 68320 KiB
sorted_3000_300.txt AC 131 ms 68456 KiB
sorted_3000_3000.txt AC 161 ms 68492 KiB