Submission #12150591

Source Code Expand

# E - Active Infants

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

# 添字のリスト
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[j] = 位置jから幅iの区間に小さい方からi個を配置したときの最大うれしさ
dp = [0] * (n + 1)

for i in range(n):
    for j in range(n - i):
        dp[j] = max(dp[j]     + a[p[i]] * abs(p[i] - (j + i)),
                    dp[j + 1] + a[p[i]] * abs(p[i] - j))

print(dp[0])

Submission Info

Submission Time
Task E - Active Infants
User ytakata69
Language Python (3.8.2)
Score 500
Code Size 486 Byte
Status AC
Exec Time 1590 ms
Memory 9400 KiB

Judge Result

Set Name Sample FULL
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 26
Set Name Test Cases
Sample Sample_01.txt, Sample_02.txt, Sample_03.txt
FULL Sample_01.txt, Sample_02.txt, Sample_03.txt, maxhand_01.txt, maxhand_02.txt, maxhand_03.txt, maxhand_04.txt, maxhand_05.txt, maxrand_01.txt, maxrand_02.txt, maxrand_03.txt, maxrand_04.txt, maxrand_05.txt, minhand_01.txt, minhand_02.txt, minhand_03.txt, minhand_04.txt, minrand_01.txt, minrand_02.txt, minrand_03.txt, minrand_04.txt, ni_01.txt, rand_01.txt, rand_02.txt, rand_03.txt, rand_04.txt
Case Name Status Exec Time Memory
Sample_01.txt AC 18 ms 8912 KiB
Sample_02.txt AC 19 ms 9076 KiB
Sample_03.txt AC 20 ms 9076 KiB
maxhand_01.txt AC 1471 ms 9312 KiB
maxhand_02.txt AC 1472 ms 9220 KiB
maxhand_03.txt AC 1485 ms 9400 KiB
maxhand_04.txt AC 1558 ms 9224 KiB
maxhand_05.txt AC 1517 ms 9196 KiB
maxrand_01.txt AC 1529 ms 9256 KiB
maxrand_02.txt AC 1506 ms 9252 KiB
maxrand_03.txt AC 1590 ms 9200 KiB
maxrand_04.txt AC 1492 ms 9196 KiB
maxrand_05.txt AC 1482 ms 9196 KiB
minhand_01.txt AC 18 ms 9016 KiB
minhand_02.txt AC 17 ms 8916 KiB
minhand_03.txt AC 19 ms 9084 KiB
minhand_04.txt AC 16 ms 8920 KiB
minrand_01.txt AC 20 ms 9080 KiB
minrand_02.txt AC 16 ms 9076 KiB
minrand_03.txt AC 17 ms 8916 KiB
minrand_04.txt AC 17 ms 9072 KiB
ni_01.txt AC 17 ms 9088 KiB
rand_01.txt AC 382 ms 9292 KiB
rand_02.txt AC 1328 ms 9376 KiB
rand_03.txt AC 867 ms 9076 KiB
rand_04.txt AC 77 ms 8924 KiB