Submission #27665738

Source Code Expand

from collections import defaultdict
N=int(input())
A=[0]+list(map(int,input().split()))
f=[0]*(N+1)

# fの前計算
# f(i) が存在しない時、f(i)=0としてしまって良い（DP[0]=0なので）
s=0
d=defaultdict(int)
for i in range(N+1):
  s+=A[i]
  f[i]=d[s]
  d[s]=i

DP=[0]*(N+1)
DP[1]=1
# 配るDP
for i in range(1,N):
  DP[i+1]=(DP[i]*2-DP[f[i]])%998244353

print(DP[N])

Submission Info

Submission Time
Task F - Predilection
User kyopro_friends
Language Python (3.8.2)
Score 500
Code Size 405 Byte
Status AC
Exec Time 254 ms
Memory 53744 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 20
Set Name Test Cases
Sample sample00, sample01
All case02, case03, case04, case05, case06, case07, case08, case09, case10, case11, case12, case13, case14, case15, case16, case17, case18, case19, sample00, sample01
Case Name Status Exec Time Memory
case02 AC 29 ms 9280 KiB
case03 AC 24 ms 9460 KiB
case04 AC 29 ms 9324 KiB
case05 AC 119 ms 21244 KiB
case06 AC 130 ms 24012 KiB
case07 AC 160 ms 29144 KiB
case08 AC 125 ms 23112 KiB
case09 AC 119 ms 21880 KiB
case10 AC 116 ms 21764 KiB
case11 AC 147 ms 25496 KiB
case12 AC 192 ms 30392 KiB
case13 AC 253 ms 41564 KiB
case14 AC 199 ms 36984 KiB
case15 AC 164 ms 26616 KiB
case16 AC 254 ms 53448 KiB
case17 AC 248 ms 53744 KiB
case18 AC 199 ms 40696 KiB
case19 AC 58 ms 16032 KiB
sample00 AC 20 ms 9460 KiB
sample01 AC 31 ms 9168 KiB