結果
| 問題 | No.919 You Are A Project Manager |
| ユーザー |
 terasa
|
| 提出日時 | 2023-01-07 14:59:24 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 369 ms / 3,000 ms |
| コード長 | 6,683 bytes |
| コンパイル時間 | 572 ms |
| コンパイル使用メモリ | 82,308 KB |
| 実行使用メモリ | 83,708 KB |
| 最終ジャッジ日時 | 2024-05-08 11:14:19 |
| 合計ジャッジ時間 | 15,020 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 234 ms
81,564 KB |
| testcase_01 | AC | 66 ms
70,872 KB |
| testcase_02 | AC | 66 ms
69,036 KB |
| testcase_03 | AC | 65 ms
69,884 KB |
| testcase_04 | AC | 110 ms
79,552 KB |
| testcase_05 | AC | 109 ms
79,372 KB |
| testcase_06 | AC | 119 ms
79,392 KB |
| testcase_07 | AC | 227 ms
81,872 KB |
| testcase_08 | AC | 155 ms
80,552 KB |
| testcase_09 | AC | 158 ms
80,480 KB |
| testcase_10 | AC | 179 ms
80,752 KB |
| testcase_11 | AC | 175 ms
80,676 KB |
| testcase_12 | AC | 101 ms
78,308 KB |
| testcase_13 | AC | 198 ms
80,728 KB |
| testcase_14 | AC | 102 ms
78,496 KB |
| testcase_15 | AC | 130 ms
79,936 KB |
| testcase_16 | AC | 199 ms
80,648 KB |
| testcase_17 | AC | 245 ms
81,524 KB |
| testcase_18 | AC | 240 ms
82,136 KB |
| testcase_19 | AC | 248 ms
82,168 KB |
| testcase_20 | AC | 317 ms
82,824 KB |
| testcase_21 | AC | 234 ms
82,004 KB |
| testcase_22 | AC | 234 ms
81,684 KB |
| testcase_23 | AC | 230 ms
81,156 KB |
| testcase_24 | AC | 232 ms
81,632 KB |
| testcase_25 | AC | 244 ms
81,756 KB |
| testcase_26 | AC | 317 ms
82,392 KB |
| testcase_27 | AC | 325 ms
82,116 KB |
| testcase_28 | AC | 336 ms
82,760 KB |
| testcase_29 | AC | 242 ms
81,660 KB |
| testcase_30 | AC | 243 ms
81,556 KB |
| testcase_31 | AC | 234 ms
81,528 KB |
| testcase_32 | AC | 242 ms
82,184 KB |
| testcase_33 | AC | 255 ms
81,920 KB |
| testcase_34 | AC | 245 ms
81,500 KB |
| testcase_35 | AC | 340 ms
82,316 KB |
| testcase_36 | AC | 344 ms
82,684 KB |
| testcase_37 | AC | 340 ms
82,788 KB |
| testcase_38 | AC | 369 ms
83,708 KB |
| testcase_39 | AC | 97 ms
78,128 KB |
| testcase_40 | AC | 130 ms
79,872 KB |
| testcase_41 | AC | 107 ms
79,304 KB |
| testcase_42 | AC | 121 ms
79,264 KB |
| testcase_43 | AC | 125 ms
79,480 KB |
| testcase_44 | AC | 146 ms
80,260 KB |
| testcase_45 | AC | 123 ms
79,660 KB |
| testcase_46 | AC | 149 ms
80,540 KB |
| testcase_47 | AC | 232 ms
81,372 KB |
| testcase_48 | AC | 226 ms
81,728 KB |
| testcase_49 | AC | 234 ms
81,552 KB |
| testcase_50 | AC | 228 ms
81,572 KB |
| testcase_51 | AC | 222 ms
81,584 KB |
| testcase_52 | AC | 230 ms
81,356 KB |
| testcase_53 | AC | 217 ms
81,788 KB |
| testcase_54 | AC | 129 ms
79,468 KB |
| testcase_55 | AC | 67 ms
69,868 KB |
| testcase_56 | AC | 67 ms
71,044 KB |
| testcase_57 | AC | 70 ms
71,996 KB |
ソースコード
from typing import List, Tuple, Callable, TypeVar, Optional
import sys
import itertools
import heapq
import bisect
import math
from collections import deque, defaultdict
from functools import lru_cache, cmp_to_key
input = sys.stdin.readline
if __file__ != 'prog.py':
sys.setrecursionlimit(10 ** 6)
def readints(): return map(int, input().split())
def readlist(): return list(readints())
def readstr(): return input()[:-1]
def readlist1(): return list(map(lambda x: int(x) - 1, input().split()))
class BitVector:
# reference: https://tiramister.net/blog/posts/bitvector/
# (reference implemention is succinct, but this implemention is not succinct.)
def __init__(self, N):
self.N = N
self.block_num = (N + 31) >> 5
self.bit = [0] * self.block_num
self.sum = [0] * self.block_num
self.built = False
def set(self, pos):
self.bit[pos >> 5] |= 1 << (pos & 31)
def build(self):
assert not self.built
for i in range(1, self.block_num):
self.sum[i] = self.sum[i - 1] + self.popcount(self.bit[i - 1])
self.built = True
def access(self, pos):
"""return pos-th bit"""
return self.bit[pos >> 5] >> (pos & 31) & 1
def rank(self, pos):
"""count 1's in [0, pos) range"""
assert self.built
i = pos >> 5
offset = pos & 31
return self.sum[i] + self.popcount(self.bit[i] & ((1 << offset) - 1))
def select(self, num):
"""return minimum i that satisfies rank(i) = num"""
assert self.built
if num == 0:
return 0
if self.rank(self.N) < num:
return -1
l = -1
r = self.N
while r - l > 1:
c = (l + r) >> 1
if self.rank(c) >= num:
r = c
else:
l = c
return r
def popcount(self, n):
c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
return c
class WaveletMatrix:
# reference: https://miti-7.hatenablog.com/entry/2018/04/28/152259
def __init__(self, A):
self.nums = sorted(set(A))
self.idx = {a: i for i, a in enumerate(self.nums)}
self.A = [self.idx[a] for a in A]
self.digit = (len(self.nums) - 1).bit_length()
self.B = [None] * self.digit
self.offset = [None] * self.digit
self.start_index = {}
T = self.A
for k in range(self.digit)[::-1]:
self.B[k] = BitVector(len(T) + 1)
zeros = []
ones = []
for i, a in enumerate(T):
if a >> k & 1:
self.B[k].set(i)
ones.append(a)
else:
zeros.append(a)
self.B[k].build()
self.offset[k] = len(zeros)
T = zeros + ones
for i, a in enumerate(T):
self.start_index.setdefault(a, i)
def access(self, i):
"""return i-th value"""
ret = 0
cur = i
for k in range(self.digit)[::-1]:
if self.B[k].access(cur):
ret |= (1 << k)
cur = self.B[k].rank(cur) + self.offset[k]
else:
cur -= self.B[k].rank(cur)
return self.nums[ret]
def rank(self, i, x):
"""return the number of x's in [0, i) range"""
x = self.idx.get(x)
if x is None:
return 0
for k in range(self.digit)[::-1]:
if x >> k & 1:
i = self.B[k].rank(i) + self.offset[k]
else:
i -= self.B[k].rank(i)
return i - self.start_index[x]
def quantile(self, l, r, n):
"""return n-th (0-indexed) smallest value in [l, r) range"""
assert 0 <= n < r - l
ret = 0
for k in range(self.digit)[::-1]:
rank_l = self.B[k].rank(l)
rank_r = self.B[k].rank(r)
ones = rank_r - rank_l
zeros = r - l - ones
if zeros <= n:
ret |= 1 << k
l = rank_l + self.offset[k]
r = rank_r + self.offset[k]
n -= zeros
else:
l -= rank_l
r -= rank_r
return self.nums[ret]
def range_freq(self, l, r, lower, upper):
"""return the number of values s.t. lower <= x < upper"""
return self.range_freq_upper(l, r, upper) - self.range_freq_upper(l, r, lower)
def prev_value(self, l, r, upper):
"""return maximum x s.t. x < upper in [l, r) range if exist, otherwise None"""
cnt = self.range_freq_upper(l, r, upper)
if cnt == 0:
return None
return self.quantile(l, r, cnt - 1)
def next_value(self, l, r, lower):
"""return minimum x s.t. x >= lower in [l, r) range if exist, otherwise None"""
cnt = self.range_freq_upper(l, r, lower)
if cnt == r - l:
return None
return self.quantile(l, r, cnt)
def range_freq_upper(self, l, r, upper):
"""return the number of values s.t. x < upper in [l, r) range"""
if l >= r:
return 0
if upper > self.nums[-1]:
return r - l
if upper <= self.nums[0]:
return 0
upper = bisect.bisect_left(self.nums, upper)
ret = 0
for k in range(self.digit)[::-1]:
rank_l = self.B[k].rank(l)
rank_r = self.B[k].rank(r)
ones = rank_r - rank_l
zeros = r - l - ones
if upper >> k & 1:
ret += zeros
l = rank_l + self.offset[k]
r = rank_r + self.offset[k]
else:
l -= rank_l
r -= rank_r
return ret
N = int(input())
A = readlist()
WM = WaveletMatrix(A)
ans = 0
for k in range(1, N + 1):
maxl = [0]
cur = 0
acc = 0
for i in range(N // k):
median = WM.quantile(cur, cur + k, (k - 1) // 2)
acc += k * median
maxl.append(max(maxl[-1], acc))
cur += k
maxr = [0]
cur = N
acc = 0
for i in range(N // k):
median = WM.quantile(cur - k, cur, (k - 1) // 2)
acc += k * median
maxr.append(max(maxr[-1], acc))
cur -= k
for i in range(N // k + 1):
s = maxl[i] + maxr[N // k - i]
ans = max(ans, s)
print(ans)