Submission #18665627


Source Code Expand

Copy
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

INF = 1 << 60

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def naive(N, P, Q, C):
    dp = np.full(N + 1, -INF, np.int64)
    dp[0] = 0
    for i in range(N):
        newdp = np.full_like(dp, -INF)
        newdp = np.maximum(newdp, dp + C[i])
        newdp[1:] = np.maximum(newdp[1:],
                               dp[:-1] + P * np.arange(Q, Q + N + N, 2))
        dp = newdp
        Q -= 1
    return dp.max()

def main(N, P, Q, C):
    A = np.arange(Q, Q + N + N, 2, dtype=np.int64)
    A = np.cumsum(A)
    A *= P
    A = np.append(0, A)
    A -= P * N * (N - 1) // 2
    C = C + np.arange(N, dtype=np.int64) * P
    C.sort()
    C = C[::-1]
    C = np.append(0, np.cumsum(C))

    A += C[::-1]
    return A.max()

N, P, Q = from_readline()
C = from_read()

# print(naive(N, P, Q, C))
print(main(N, P, Q, C))

Submission Info

Submission Time
Task D - 夕食
User maspy
Language Python (3.8.2)
Score 100
Code Size 1152 Byte
Status AC
Exec Time 186 ms
Memory 46904 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 35
Set Name Test Cases
All 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 05_challengeeasy_00, 05_negative_00, 10_SmallRandom_00, 10_SmallRandom_01, 10_SmallRandom_02, 10_SmallRandom_03, 10_SmallRandom_04, 20_SmallRandom_00, 20_SmallRandom_01, 20_SmallRandom_02, 20_SmallRandom_03, 20_SmallRandom_04, 50_LargeRandom_00, 50_LargeRandom_01, 50_LargeRandom_02, 51_Max_00, 51_Max_01, 60_LargeRandom_00, 60_LargeRandom_01, 60_LargeRandom_02, 60_LargeRandom_03, 70_LargeRandom_00, 70_LargeRandom_01, 70_LargeRandom_02, 80_LargeRandom_00, 80_LargeRandom_01, 80_LargeRandom_02, 80_LargeRandom_03, 80_LargeRandom_04, 80_LargeRandom_05, 80_LargeRandom_06
Case Name Status Exec Time Memory
00_sample_01 AC 128 ms 27264 KB
00_sample_02 AC 112 ms 27044 KB
00_sample_03 AC 112 ms 27028 KB
00_sample_04 AC 113 ms 27084 KB
05_challengeeasy_00 AC 110 ms 27208 KB
05_negative_00 AC 110 ms 27000 KB
10_SmallRandom_00 AC 109 ms 27052 KB
10_SmallRandom_01 AC 115 ms 27084 KB
10_SmallRandom_02 AC 114 ms 27248 KB
10_SmallRandom_03 AC 111 ms 27212 KB
10_SmallRandom_04 AC 109 ms 26960 KB
20_SmallRandom_00 AC 115 ms 27064 KB
20_SmallRandom_01 AC 114 ms 27208 KB
20_SmallRandom_02 AC 111 ms 27004 KB
20_SmallRandom_03 AC 111 ms 26996 KB
20_SmallRandom_04 AC 112 ms 26776 KB
50_LargeRandom_00 AC 158 ms 46520 KB
50_LargeRandom_01 AC 164 ms 46728 KB
50_LargeRandom_02 AC 158 ms 46652 KB
51_Max_00 AC 156 ms 46588 KB
51_Max_01 AC 152 ms 46740 KB
60_LargeRandom_00 AC 186 ms 46612 KB
60_LargeRandom_01 AC 183 ms 46656 KB
60_LargeRandom_02 AC 184 ms 46904 KB
60_LargeRandom_03 AC 183 ms 46400 KB
70_LargeRandom_00 AC 150 ms 46748 KB
70_LargeRandom_01 AC 159 ms 46816 KB
70_LargeRandom_02 AC 155 ms 46396 KB
80_LargeRandom_00 AC 166 ms 46820 KB
80_LargeRandom_01 AC 163 ms 46816 KB
80_LargeRandom_02 AC 168 ms 46604 KB
80_LargeRandom_03 AC 165 ms 46604 KB
80_LargeRandom_04 AC 168 ms 46564 KB
80_LargeRandom_05 AC 166 ms 46708 KB
80_LargeRandom_06 AC 164 ms 46616 KB