Submission #11811746


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict

INF = 10 ** 18

N, *A = map(int, read().split())
dp_not = defaultdict(lambda: -INF)
dp_take = defaultdict(lambda: -INF)
dp_not[(0, 0)] = 0

for i, x in enumerate(A, 1):
    j = (i - 1) // 2
    for n in (j, j + 1):
        dp_not[(i, n)] = max(dp_not[(i - 1, n)], dp_take[(i - 1, n)])
        dp_take[(i, n)] = dp_not[(i - 1, n - 1)] + x

print(max(dp_not[(N, N // 2)], dp_take[(N, N // 2)]))

Submission Info

Submission Time
Task F - Select Half
User maspy
Language Python (3.8.2)
Score 600
Code Size 566 Byte
Status
Exec Time 919 ms
Memory 192592 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01, sample_02, sample_03, sample_04
All 600 / 600 hand_01, hand_02, max_01, max_02, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
hand_01 18 ms 9336 KB
hand_02 19 ms 9412 KB
max_01 871 ms 192592 KB
max_02 874 ms 191124 KB
random_01 888 ms 189244 KB
random_02 902 ms 189148 KB
random_03 896 ms 189252 KB
random_04 896 ms 189320 KB
random_05 890 ms 189464 KB
random_06 912 ms 189344 KB
random_07 916 ms 189260 KB
random_08 919 ms 189260 KB
random_09 902 ms 192476 KB
random_10 915 ms 191032 KB
sample_01 20 ms 9284 KB
sample_02 18 ms 9332 KB
sample_03 20 ms 9332 KB
sample_04 19 ms 9336 KB