Submission #55020280

Source Code Expand

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
f = [defaultdict(int) for _ in range(n)]
g = [0] * n
ans = 1
for i in range(n):
    tmp = defaultdict(int)
    g[i] = 1
    for j in range(i):
        tmp[a[i] + a[j]] = max(tmp[a[i] + a[j]], g[j])
        for x in f[j]:
            if x == 0:
                g[i] += f[j][x]
                continue
            f[i][a[i] + x] = (f[j][x] + f[i][a[i] + x]) % MOD
    for x in tmp:
        if x != a[i]:
            f[i][x] += tmp[x]
    for x in f[i]:
        # print(i, x, f[i][x])
        if x == a[i]:
            continue
        ans += f[i][x]
        ans %= MOD
        
print(ans)

Submission Info

Submission Time
Task C - Subsequence and Prefix Sum
User yefllower
Language Python (PyPy 3.10-v7.3.12)
Score 600
Code Size 723 Byte
Status AC
Exec Time 108 ms
Memory 84172 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 4
AC × 30
Set Name Test Cases
Sample 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt, 00-sample-004.txt
All 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt, 00-sample-004.txt, 01-001.txt, 01-002.txt, 01-003.txt, 01-004.txt, 01-005.txt, 01-006.txt, 01-007.txt, 01-008.txt, 01-009.txt, 01-010.txt, 01-011.txt, 01-012.txt, 01-013.txt, 01-014.txt, 01-015.txt, 01-016.txt, 01-017.txt, 01-018.txt, 01-019.txt, 01-020.txt, 01-021.txt, 01-022.txt, 01-023.txt, 01-024.txt, 01-025.txt, 01-026.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 65 ms 76828 KiB
00-sample-002.txt AC 66 ms 76952 KiB
00-sample-003.txt AC 65 ms 76620 KiB
00-sample-004.txt AC 76 ms 82564 KiB
01-001.txt AC 66 ms 76868 KiB
01-002.txt AC 83 ms 84172 KiB
01-003.txt AC 83 ms 83876 KiB
01-004.txt AC 91 ms 83640 KiB
01-005.txt AC 77 ms 82304 KiB
01-006.txt AC 82 ms 83696 KiB
01-007.txt AC 84 ms 83564 KiB
01-008.txt AC 84 ms 84104 KiB
01-009.txt AC 75 ms 82196 KiB
01-010.txt AC 84 ms 83576 KiB
01-011.txt AC 76 ms 82440 KiB
01-012.txt AC 72 ms 82148 KiB
01-013.txt AC 69 ms 81568 KiB
01-014.txt AC 83 ms 83848 KiB
01-015.txt AC 89 ms 83616 KiB
01-016.txt AC 89 ms 83144 KiB
01-017.txt AC 92 ms 83624 KiB
01-018.txt AC 95 ms 83524 KiB
01-019.txt AC 100 ms 83592 KiB
01-020.txt AC 103 ms 83508 KiB
01-021.txt AC 106 ms 83476 KiB
01-022.txt AC 104 ms 83556 KiB
01-023.txt AC 108 ms 84096 KiB
01-024.txt AC 69 ms 81796 KiB
01-025.txt AC 79 ms 81924 KiB
01-026.txt AC 79 ms 82340 KiB