Contest Duration: - (local time) (300 minutes) Back to Home

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 2020-12-10 13:25:31+0900 D - 夕食 maspy Python (3.8.2) 100 1152 Byte AC 186 ms 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