Submission #55346792

Source Code Expand

import sys

input = sys.stdin.readline

mod = 998244353

N = int(input())
A = list(map(int, input().split()))
dp = [None] * N
idx = [None] * N
for i in range(N)[::-1]:
    diffs = list(set([A[j] - A[i] for j in range(i + 1, N)]))
    idx[i] = {d: k for k, d in enumerate(diffs)}
    dp[i] = [[0] * len(diffs) for _ in range(N + 1)]

    for j in range(i + 1, N):
        d = A[j] - A[i]
        di = idx[i][d]
        dp[i][2][di] += 1
        if d not in idx[j]:
            continue
        dj = idx[j][d]
        for l in range(2, N - i):
            dp[i][l + 1][di] = (dp[i][l + 1][di] + dp[j][l][dj]) % mod
ans = [0] * (N + 1)
ans[1] = N
for i in range(N):
    for l in range(2, N - i + 1):
        ans[l] = (ans[l] + sum(dp[i][l])) % mod
print(*ans[1:])

Submission Info

Submission Time
Task E - Count Arithmetic Subsequences
User sotanishy
Language Python (PyPy 3.10-v7.3.12)
Score 475
Code Size 791 Byte
Status AC
Exec Time 70 ms
Memory 82628 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 54 ms 76744 KiB
00_sample_02.txt AC 54 ms 76224 KiB
00_sample_03.txt AC 54 ms 76252 KiB
01_random_01.txt AC 62 ms 81272 KiB
01_random_02.txt AC 69 ms 82044 KiB
01_random_03.txt AC 69 ms 81956 KiB
01_random_04.txt AC 69 ms 82000 KiB
01_random_05.txt AC 57 ms 80404 KiB
01_random_06.txt AC 65 ms 81624 KiB
01_random_07.txt AC 54 ms 76240 KiB
01_random_08.txt AC 68 ms 82476 KiB
01_random_09.txt AC 54 ms 76460 KiB
01_random_10.txt AC 68 ms 82628 KiB
01_random_11.txt AC 65 ms 81816 KiB
01_random_12.txt AC 65 ms 81988 KiB
01_random_13.txt AC 59 ms 80740 KiB
01_random_14.txt AC 65 ms 81624 KiB
01_random_15.txt AC 65 ms 81956 KiB
01_random_16.txt AC 65 ms 81632 KiB
01_random_17.txt AC 65 ms 81696 KiB
01_random_18.txt AC 65 ms 81548 KiB
01_random_19.txt AC 68 ms 82384 KiB
01_random_20.txt AC 65 ms 81908 KiB
02_handmade_01.txt AC 65 ms 81728 KiB
02_handmade_02.txt AC 66 ms 82040 KiB
02_handmade_03.txt AC 69 ms 82072 KiB
02_handmade_04.txt AC 69 ms 82044 KiB
02_handmade_05.txt AC 70 ms 82116 KiB
02_handmade_06.txt AC 70 ms 82340 KiB