Submission #55421717

Source Code Expand

from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))

# dp[i][k][d]=長さがk、交差がd、末尾がa[i]
dp=[[defaultdict(int) for _ in range(N+1)] for _ in range(N+1)]

for n in range(N):
  for prev in range(n):
    d=A[n]-A[prev]
    for k in range(n+1):
      dp[n][k+1][d]+=dp[prev][k][d]
    dp[n][2][d]+=1

print(N)
for k in range(2,N+1):
  print(sum(sum(dp[n][k].values()) for n in range(N))%998244353)

Submission Info

Submission Time
Task E - Count Arithmetic Subsequences
User kyopro_friends
Language Python (PyPy 3.10-v7.3.12)
Score 475
Code Size 459 Byte
Status AC
Exec Time 133 ms
Memory 95160 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 3
AC × 29
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 76 ms 76972 KiB
00_sample_02.txt AC 74 ms 76816 KiB
00_sample_03.txt AC 74 ms 76728 KiB
01_random_01.txt AC 103 ms 84076 KiB
01_random_02.txt AC 120 ms 84712 KiB
01_random_03.txt AC 120 ms 84552 KiB
01_random_04.txt AC 117 ms 84192 KiB
01_random_05.txt AC 91 ms 83844 KiB
01_random_06.txt AC 130 ms 94832 KiB
01_random_07.txt AC 73 ms 76648 KiB
01_random_08.txt AC 126 ms 94716 KiB
01_random_09.txt AC 72 ms 76732 KiB
01_random_10.txt AC 127 ms 94820 KiB
01_random_11.txt AC 106 ms 84816 KiB
01_random_12.txt AC 128 ms 94540 KiB
01_random_13.txt AC 96 ms 84860 KiB
01_random_14.txt AC 130 ms 94756 KiB
01_random_15.txt AC 115 ms 84824 KiB
01_random_16.txt AC 133 ms 94416 KiB
01_random_17.txt AC 114 ms 84988 KiB
01_random_18.txt AC 128 ms 94900 KiB
01_random_19.txt AC 101 ms 84796 KiB
01_random_20.txt AC 128 ms 95160 KiB
02_handmade_01.txt AC 94 ms 84344 KiB
02_handmade_02.txt AC 102 ms 85144 KiB
02_handmade_03.txt AC 130 ms 94136 KiB
02_handmade_04.txt AC 131 ms 94272 KiB
02_handmade_05.txt AC 133 ms 94476 KiB
02_handmade_06.txt AC 130 ms 94424 KiB